Module: (Python) Prática 4. Algoritmo de Euclides


Problem

6 /6


Tarefa para Petya e Vanya

Problem

Os alunos da quinta série Petya e Vanya aprenderam o seguinte algoritmo de Euclides na aula de matemática:

  1. Deixe a, b — os números a serem encontrados.

  2. Se b = 0 então o número a — GCD que você está procurando.

  3. Se b > a então troque os números a e b .< /p>

  4. Defina um a valor a – b.

  5. Volte para a etapa 2.

Masha criou uma tarefa para eles consertarem. Ela pediu aos meninos que inventassem os números a, b, c e d que no processo de implementação do algoritmo de Euclides para um determinado par de números (a, b) , chega um momento em que, antes da etapa 2 ser executada, o número a  será igual a c , e o número b será igual a d.

Escreva um programa para Masha para verificar se os números satisfazem a, b, c, d Condições de Masha.

Entrada: A primeira linha da entrada contém o número de casos de teste K ( \( 1 <= K <= 100\)). Abaixo estão as descrições desses conjuntos. Cada descrição consiste em duas linhas. O primeiro contém dois inteiros: a, b (\(1 <= a, \ b <= 10^{18}\)). A segunda linha – dois inteiros: c, d (\(1 <= c,\ d < = 10^{18}\)).
Todos os números nas linhas são separados por espaços.

Saída: Para cada caso de teste, imprima a palavra «SIM» se durante a aplicação do algoritmo de Euclides a um par de números (a, b) em algum ponto um par é obtido (c, d< /código>). Caso contrário, imprima a palavra "NÃO".

 

Exemplos
# Entrada Saída
1 2
20 10
10 10
10 7
24		 SIM
NÃO

 

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!