GCD (MDC) – Algoritmo de Euclides
Depois de executar várias iterações do algoritmo, começamos a perceber que existem algumas operações redundantes, e o processo de encontrar o máximo divisor comum pode, na verdade, ser otimizado.
Usando subtração, continuamos a subtrair o número menor do número maior até obtermos 0 ou um valor que seja igual ao MDC. Podemos acelerar esse procedimento ao encontrar o resto da divisão do número maior pelo número menor. Com a operação de módulo, dividimos repetidamente o número maior pelo menor e tomamos o resto até que esse resto seja 0. O último resto não nulo que obtemos é o MDC.
Pense na operação de módulo como um modo mais eficiente de encontrar o MDC. Em vez de subtrair continuamente o número menor do número maior, utilizamos a divisão para reduzir o número maior. Isso significa que estamos dividindo ambos os números pelos seus divisores comuns e, assim, convergindo para o maior divisor comum de forma muito mais rápida.
a, b = int(input()), int(input())
while a > 0 and b > 0: # Se a ou b for 0 => o outro será o GCD
a, b = b, a % b # O gcd de (a, b) é o mesmo que o gcd de (b, a % b)
d = b if a == 0 else a # se a = 0 => b é o GCD, se b = 0 => a é o GCD
print('gcd:', d)Este algoritmo foi mencionado pela primeira vez no livro de Euclides, escrito em 300 a.C.
Vamos fazer algumas simulações do algoritmo:
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ GCD = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ GCD = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ GCD = 1
Entrada
A única linha da entrada contém dois inteiros
a e b (0 ≤ a, b ≤ ).Saída
O programa deve imprimir o máximo divisor comum de
a e b.Exemplos
Input | Output |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB