Máximo común divisor P30330


Statement
 

pdf   zip

thehtml

¿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):

     
mcd(58861927, 40236439) = mcd(40236439, 18625488)          
 = mcd(18625488, 2985463)          
 = mcd(2985463, 712710)          
 = mcd(712710, 134623)          
 = mcd(134623, 39595)          
 = mcd(39595, 15838)          
 = mcd(15838, 7919)          
 = mcd(7919, 0)          
 = 7919.          

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<109.  ‍50 Puntos ‍
  • Large:  ‍ Entradas con a,b<1017.  ‍50 Puntos ‍
Public test cases
  • Input

    58861927 40236439
    40236439 58861927
    1 1
    13 15
    24 28
    99 55
    191 42
    2924 3931
    

    Output

    7919
    7919
    1
    1
    4
    11
    1
    1
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++