Least Common Multiple
Recibes dos enteros positivos a y b. Devuelve su mínimo común múltiplo: el menor entero positivo por el que tanto a como b son divisibles sin dejar residuo.
Función
- ainteger
- el primer entero positivo
- binteger
- el segundo entero positivo
- Devuelveinteger
- el menor entero positivo que es múltiplo tanto de a como de b
Restricciones
1 ≤ a ≤ 1061 ≤ b ≤ 106- La respuesta cabe en un entero de 32 bits con signo:
lcm(a, b) ≤ 231-1. El productoa × bquizá no.
Ejemplos
- Entrada
- a = 4b = 6
- Salida
- 12
- Explicación
- Los múltiplos de
6empiezan por 6, 12, 18; los múltiplos de4empiezan por 4, 8, 12. El primer número que aparece en ambas listas es12.
- Entrada
- a = 7b = 3
- Salida
- 21
- Explicación
7y3no comparten ningún factor aparte de1, así que su mínimo común múltiplo es su producto,21.
- Entrada
- a = 15b = 45
- Salida
- 45
- Explicación
15divide a45exactamente, así que45ya es múltiplo de ambos y no existe ningún múltiplo menor de45.
Para ir más allá
¿Puedes encontrar el mcd sin usar divisiones ni restos, usando solo restas y divisiones entre dos?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
La respuesta es un múltiplo del número mayor. ¿Necesitas probar todos los números intermedios o solo los múltiplos del número mayor?
El máximo común divisor y el mínimo común múltiplo están relacionados:
gcd(a, b) × lcm(a, b) = a × b. El algoritmo de Euclides encuentra el máximo común divisor en unas pocas docenas de pasos.Calcula el máximo común divisor y después devuelve
a / gcd × b. Divide primero: el productoa × bpuede desbordar un entero de 32 bits aunque la respuesta quepa.
Solución
El mínimo común múltiplo y el máximo común divisor están relacionados por una propiedad: gcd(a, b) × lcm(a, b) = a × b. Así que la respuesta rápida es a × b / gcd(a, b). El producto puede alcanzar 10^12 y desbordar un entero de 32 bits aunque la respuesta quepa, así que divide por el MCD antes de multiplicar.
Cuenta hacia arriba desde el número mayor
Correcto, pero no termina con las pruebas más grandes
Intuición
La respuesta es al menos el número mayor. Empieza con m en max(a, b) y suma 1 hasta que ambos números lo dividan; pruebas candidatos en orden creciente, así que el primero que funciona es el menor. Para 4 y 6, pruebas del 6 al 11 y te detienes en 12. El bucle siempre termina, porque a × b es un múltiplo común.
El número de intentos es aproximadamente del tamaño de la respuesta. Para los números primos 46337 y 46327, la respuesta es 2146654199: más de dos mil millones de intentos.
Algoritmo
- Asigna a
mel mayor valor entreayb. - Mientras
m % aom % bno sea0, suma 1 am. - Devuelve
m.
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return mAvanza en múltiplos del número mayor
Intuición
La respuesta debe ser un múltiplo del número mayor, big, así que avanza de big en 2 × big, 3 × big y detente en el primero que sea divisible por el número menor. Para 4 y 6, pruebas 6 y después 12.
Como small × big siempre es un múltiplo común, el bucle se ejecuta como máximo min(a, b) veces, como máximo un millón en este caso. Es lo bastante rápido para estos límites, pero sigue creciendo con la entrada; con números de hasta 10^18, no lo sería.
Algoritmo
- Sea
bigel número mayor ysmallel menor. - Asigna
m = big. - Mientras
m % smallno sea0, sumabigam. - Devuelve
m.
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return mDivide por el MCD y después multiplica
Intuición
Descompón ambos números en factores primos. Para cada primo, el mcd toma la menor de sus dos potencias y el mcm la mayor, así que juntos usan cada factor de a y de b exactamente una vez: gcd × lcm = a × b. Para 4 = 2² y 6 = 2 × 3, el mcd es 2 y el mcm es 2² × 3 = 12.
El algoritmo de Euclides encuentra el mcd en O(log(min(a, b))) pasos. Después, calcula a / gcd × b en ese orden: el mcd divide a a exactamente, así que no se pierde nada y ningún paso supera la respuesta. a × b / gcd desborda un entero de 32 bits con a = b = 10^6, donde el producto es 10^12 y la respuesta es solo 10^6.
Algoritmo
- Copia
aybenxyy. - Mientras
yno sea0, reemplaza(x, y)por(y, x % y). Ahoraxes el MCD. - Divide
aentrex. - Multiplica el resultado por
by devuélvelo.
def lcm(a, b):
x, y = a, b
while y != 0:
x, y = y, x % y
# x is gcd(a, b). Divide before multiplying.
return a // x * b
Errores comunes y casos límite
- Calcular primero
a × b. En Java, C, C++, C# y Rust, el producto de dos números cercanos a10^6desborda un entero de 32 bits y da un resultado incorrecto o negativo (una compilación de depuración de Rust entra en pánico), aunque el mcm quepa. - Dividir en coma flotante. El resultado puede ser
2.146654199E9o perder sus últimos dígitos; mantén todo en números enteros. - Ejecutar el bucle de Euclides sobre
ayb. Después contienen el mcd y0, así que trabaja con copias. - Suponer que la respuesta es
a × b. Eso solo se cumple cuando los números no comparten ningún factor:lcm(4, 6)es12, no24.
Preguntas frecuentes3
¿Cuál es la fórmula para calcular el MCM de dos números?
lcm(a, b) = a × b / gcd(a, b), calculado como a / gcd(a, b) × b para que ningún valor intermedio supere la respuesta. Para 4 y 6, el gcd es 2, y 4 / 2 × 6 = 12.
¿Cuál es la complejidad temporal de calcular el MCM?
Con la fórmula del mcd, el tiempo es O(log(min(a, b))), el coste del algoritmo de Euclides, y el espacio es O(1). Avanzar en múltiplos del número mayor es O(min(a, b)), y contar de uno en uno es O(lcm(a, b)).
¿Cómo se calcula el MCM de más de dos números?
Pliega la lista: lcm(a, b, c) = lcm(lcm(a, b), c). Para [4, 6, 10], lcm(4, 6) = 12 y lcm(12, 10) = 60. El valor acumulado crece rápidamente, así que usa enteros de 64 bits cuando la lista sea larga.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def lcm(a, b):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
a = 4 b = 6
Salida Esperada
12