Maior divisor comum (MDC) com subtração

Dadas duas variáveis inteiras positivas a e b, pede-se que se calcule o maior divisor comum de ambas. Contudo, desta vez os números são bem maiores. Portanto, tentar listar todos os divisores de cada número e verificar qual o maior divisor em comum não é viável. Precisamos otimizar o algoritmo.

Vamos considerar o caso em que a > b. Se pensarmos em um divisor comum d, tanto a quanto b são divisíveis por d. Isto significa:

Assim, d é divisor tanto de a quanto de b. E como tanto x quanto y são inteiros ⇒ x-y também é inteiro. Portanto, se a - b = d(x-y), d também é um divisor de b - a. Essa constatação é muito útil e pode otimizar o número de passos necessários para encontrar o MDC.

Se o maior divisor comum d divide a, b e também a-b, podemos encontrar d calculando diretamente o MDC de b e a-b em vez de usar a, que era maior. Podemos repetir esse processo até que a ou b seja 0 (caso em que o elemento não nulo é o maior divisor):

a, b = int(input()), int(input())
while a > 0 and b > 0:  # Se a ou b for 0 => o outro é o MDC
    if b > a:           # Vamos sempre manter a >= b
        a, b = b, a     # Troca dos valores
    a, b = a - b, b     # O mdc de (a, b) é o mesmo que o mdc de (a, b - a)

d = b if a == 0 else a  # se a for 0 => b é o MDC, se b for 0 => a é o MDC
print('gcd:', d)

Vejamos algumas simulações do algoritmo:

Entrada

A única linha de entrada contém dois inteiros a e b (0 ≤ a, b ≤ ).

Saída

O programa deve imprimir o maior divisor comum de a e b.

Exemplos