Module: (Python) Pratica 4. Algoritmo di Euclide


Problem

6 /6


Compito per Petya e Vanja

Problem

Gli alunni di quinta elementare Petya e Vanya hanno imparato il seguente algoritmo di Euclide durante le lezioni di matematica:

  1. Diamo a, b — i numeri da trovare.

  2. Se b = 0 allora numero a — GCD che stai cercando.

  3. Se b > a allora scambia i numeri a e b .< /p>

  4. Imposta un a valore a – b.

  5. Torna al passaggio 2.

Masha ha pensato a un compito da risolvere. Ha chiesto ai ragazzi di trovare tali numeri a, b, c e d che nel processo di implementazione dell'algoritmo di Euclide per una data coppia di numeri (a, b) , arriva un momento in cui, prima dell'esecuzione del passaggio 2, il numero a  sarà uguale a c e il numero b sarà uguale a d.

Scrivi un programma per Masha per controllare se i numeri soddisfano a, b, c, d Le condizioni di Masha.

Input: La prima riga dell'input contiene il numero di test case K ( \( 1 <= K <= 100\)). Di seguito sono riportate le descrizioni di questi set. Ogni descrizione è composta da due righe. Il primo contiene due numeri interi: a, b (\(1 <= a, \ b <= 10^{18}\)). La seconda riga – due numeri interi: c, d (\(1 <= c,\ d < = 10^{18}\)).
Tutti i numeri nelle righe sono separati da spazi.

Output: Per ogni test case, emetti la parola «YES» se durante l'applicazione dell'algoritmo di Euclide a una coppia di numeri (a, b) ad un certo punto si ottiene una coppia (c, d< /codice>). Altrimenti, emetti la parola "NO".

 

Esempi
# Input Uscita
1 2
20 10
10 10
10 7
24		 SÌ
NO

 

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!