Algoritmos y Estructuras de Datos

Máximo común divisor (GCD) con resta

Dadas dos cifras enteras positivas a y b, se te solicita calcular el máximo común divisor de ambas. Esta vez, sin embargo, los números son mucho más grandes, por lo que buscar todos los divisores de cada uno para luego encontrar el mayor en común no sería práctico. Es necesario optimizar el algoritmo.
Consideremos el caso a > b. Si pensamos en un divisor común d, tanto a como b son divisibles por d. Esto significa que:
donde x y y son algunos enteros. Si restamos b de a, obtenemos:
 
Entonces, d es divisor tanto de a como de b, y como x y y son enteros ⇒ x-y también es un entero. Por lo tanto, dado que a-b = d(x-y), d debe ser un divisor de a-b. Esta observación resulta muy útil y puede optimizar la cantidad de pasos que realizamos en nuestro programa para encontrar el GCD.
Si el máximo común divisor d divide tanto a a como a b, y también a a-b, podemos hallar d buscando el máximo común divisor de b y a-b en lugar de a (que era un número más grande). Podemos repetir este proceso hasta que a o b sea 0 (en cuyo caso, el elemento distinto de cero es el divisor más grande):
a, b = int(input()), int(input())
while a > 0 and b > 0:  # En caso de que a o b sea 0 => el otro es el GCD
    if b > a:           # Vamos a mantener a >= b
        a, b = b, a     # Intercambiamos los números
    a, b = a - b, b     # el gcd de (a, b) es el mismo que el gcd de (a, b - a)

d = b if a == 0 else a  # si a es 0 => b es GCD, si b es 0 => a es GCD
print('gcd:', d)
Realicemos algunas simulaciones del algoritmo:
a = 8, b = 12
  1. b > a ⇒ swap ⇒ a = 12, b = 8
  1. b > a ⇒ swap ⇒ a = 8, 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
  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
  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

La única línea de la entrada contiene dos enteros a y b (0 ≤ a, b ≤ ).

Salida

El programa debe imprimir el máximo común divisor de a y b.

Ejemplos

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