Module: (Python) Thực hành 4. Thuật toán Euclid


Problem

6 /6


Nhiệm vụ cho Petya và Vanya

Problem

Học sinh lớp năm Petya và Vanya đã học thuật toán Euclid sau trong lớp toán:

  1. Hãy a, b — các số cần tìm.

  2. Nếu b = 0 thì số a — GCD mà bạn đang tìm kiếm.

  3. Nếu b > a thì hoán đổi các số a và b .< /p>

  4. Đặt a giá trị a – b.

  5. Quay lại bước 2.

Masha đưa ra một nhiệm vụ để họ khắc phục. Cô yêu cầu các cậu bé nghĩ ra những con số a, b, c và d mà trong quá trình triển khai thuật toán Euclid cho một cặp số (a, b) đã cho, sẽ có lúc, trước khi thực hiện bước 2, số a  sẽ bằng c và số b sẽ bằng d.

Viết chương trình để Masha kiểm tra xem các số có thỏa mãn a, b, c, d Điều kiện của Masha.

Đầu vào: Dòng đầu tiên của đầu vào chứa số lượng trường hợp kiểm tra K ( \( 1 <= K <= 100\)). Dưới đây là mô tả của các bộ này. Mỗi mô tả bao gồm hai dòng. Số đầu tiên chứa hai số nguyên: a, b (\(1 <= a, \ b <= 10^{18}\)). Dòng thứ hai – hai số nguyên: c, d (\(1 <= c,\ d < = 10^{18}\)).
Tất cả các số trong các dòng được phân tách bằng dấu cách.

Đầu ra: Đối với mỗi trường hợp thử nghiệm, hãy xuất từ ​​«YES» nếu trong khi áp dụng thuật toán Euclid đến một cặp số (a, b) tại một thời điểm nào đó sẽ thu được một cặp (c, d< /mã>). Nếu không, hãy xuất từ ​​"KHÔNG".

 

Ví dụ
<đầu>

 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Đầu vào Đầu ra
1 2
20 10
10 10
10 7
24		 CÓ
KHÔNG