Mínimo Común Múltiplo (LCM)
El mínimo común múltiplo de dos números
a y b es el número más pequeño que es divisible tanto por a como por b. En otras palabras, buscamos un número l (el mínimo común múltiplo) de modo que y , donde x e y son enteros positivos (2 ≤ x, y).Un enfoque ingenuo sería iterar sobre los múltiplos de
a (1·a, 2·a, 3·a, ...) y comprobar cuándo alguno de ellos es divisible por b. Sin embargo, este método puede resultar muy lento. Imagina que a y b son 13 y 17. En ese caso, tendríamos que calcular 1·13, 2·13, … hasta 17·13 para encontrar finalmente un número que sea divisible por ambos.En realidad, sabemos que
a·b siempre es un múltiplo común de a y b, aunque no siempre es el más pequeño. En el caso de 13 y 17 sí resultó ser el menor, pero en otros casos como 8 y 12 no lo es. De manera general, el LCM de a y b se puede calcular como el producto de a y b, dividido por su máximo común divisor:La razón de esta fórmula radica en que el LCM es el múltiplo más pequeño de ambos números que incluye todos los factores primarios que tienen en común. Dado que el máximo común divisor de dos números es el producto de todos sus factores primarios comunes, entonces al dividir el producto de los números por su máximo común divisor, eliminamos los factores repetidos y obtenemos justamente el LCM.
Para encontrar el LCM de dos números, primero se determina la factorización en primos de ambos y luego se multiplican las potencias máximas de cada primo que aparecen en cualquiera de las dos factorizaciones.
En este caso, el producto
a·b contiene todos los factores primarios de ambos números con exponentes sumados. Al dividir por gcd(a, b) se restan los exponentes mínimos de cada factor, dejando únicamente las potencias máximas de cada factor. Esto da como resultado exactamente el LCM de a y b.Entrada
La única línea de la entrada contiene dos enteros
a y b (1 ≤ a, b ≤ ).Salida
El programa debe imprimir el mínimo común múltiplo de
a y b.Ejemplos
Entrada | Salida |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB