Mínimo múltiplo comum (LCM)
O mínimo múltiplo comum de dois números
a e b é o menor número que é divisível por ambos a e b. Assim, podemos encontrar um número l (least common multiple) tal que e , em que x e y são inteiros positivos (2 ≤ x, y).Uma abordagem ingénua seria iterar pelos múltiplos de
a (1·a, 2·a, 3·a, …) e verificar se algum deles é divisível por b. No entanto, isto pode demorar demasiado. Imagine que a e b são 13 e 17. Nesse caso, teríamos de calcular 1·13, 2·13, …, até 17·13 para finalmente chegar a um número divisível por ambos.Na verdade, sabemos que
a·b é sempre um múltiplo comum de a e b, mas pode não ser o menor. No caso de 13 e 17, era o menor, mas em outras situações, como 8 e 12, já não é. Em geral, a LCM de a e b é igual ao produto de a e b dividido pelo seu greatest common divisor (gcd):A intuição por detrás desta fórmula baseia-se no facto de a LCM ser o menor múltiplo de ambos os números que contém todos os seus fatores primos comuns. Como o greatest common divisor de dois números corresponde ao produto de todos os seus fatores primos comuns, podemos obter a LCM ao dividir o produto desses números pelo gcd, removendo os fatores duplicados.
Para encontrar a LCM de dois números, primeiro determinamos a fatorização primária de cada um deles e depois multiplicamos a maior potência de cada primo que surgir em qualquer uma das fatorizações.
Neste contexto, o produto
a·b inclui todos os fatores primos de a e b com os expoentes somados. Já gcd(a, b) remove o mínimo dos expoentes de cada fator do produto, deixando o máximo de cada fator — o que corresponde exatamente à LCM de a e b.Entrada
A única linha da entrada contém dois inteiros
a e b (1 ≤ a, b ≤ ).Saída
O programa deve imprimir o mínimo múltiplo comum de
a e b.Exemplos
Entrada | Saída |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB