Algoritmos e Estruturas de Dados

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:
onde x e y são inteiros. Se subtrairmos b de a, obtemos:
 
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:
a = 8, b = 12
  1. b > a ⇒ swap ⇒ a = 12, b = 8 a = 12 - 8 = 4, b = 8
  1. b > a ⇒ swap ⇒ a = 8, b = 4 a = 8 - 4 = 4, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. break ⇒ GCD = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. b > a ⇒ swap ⇒ a = 24, b = 6 a = 24 - 6 = 18, b = 6
  1. a = 18 - 6 = 12, b = 6
  1. a = 12 - 6 = 6, b = 6
  1. a = 6 - 6 = 0, b = 6
  1. break ⇒ GCD = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. b > a ⇒ swap ⇒ a = 16, b = 1 a = 16 - 1 = 15, b = 1
  1. a = 14, b = 1
  1. a = 13, b = 1
  1. a = 12, b = 1
  1. …
  1. …
  1. a = 0, b = 1
  1. break ⇒ GCD = 1

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

Input
Output
8 12
4
54 24
6
17 16
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue