Máximo común divisor P30330

¿Cómo calcular el máximo común divisor de dos números a y b? El método que se os habrá enseñado en clase consiste en descomponer los números a y b en primos, y luego mirar cuántos primos comunes aparecen. Este método es útil si los números a y b se dejan descomponer en primos fácilmente; ¿y cuando esto no es así? Intenta calcular el máximo común divisor de a=58861927 y b=40236439, y enseguida verás qué quiero decir.

Por suerte, Euclides ya sabía cómo resolver este problema (y tú también deberías saberlo si has ojeado las soluciones de varios problemas propuestos en anteriores concursos). Basta con aplicar las siguientes reglas (recursivas):

• Si b=0, mcd(a,b)=a.
• Si no, mcd(a,b)=mcd(b,a% b), donde a% b es el resto de la división de a entre b.

Y ya está: basta con repetir el segundo paso una y otra vez hasta que encuentres un 0. Funciona como por arte de magia [Footnote: La explicación de por qué funciona no es en absoluto complicada, y seguro que la encontrarás por Internet], y es tan sencillo que puede calcularse fácilmente a mano (aunque, por supuesto, te pediremos que lo hagas con ordenador):

Entrada

Una secuencia de casos de entrada. Cada caso es un par de números positivos a y b en una línea, separados por un espacio.

Salida

Tantas líneas como casos de entrada. Para cada caso, escribe el mcd de a y b.

Puntuación

• Small:  ‍ Entradas con a,b<10⁹.  ‍50 Puntos ‍

• Large:  ‍ Entradas con a,b<10¹7.  ‍50 Puntos ‍