Least Common Multiple

Q: ¿Cuál es la fórmula del MCM de dos números?

lcm(a, b) = a × b / gcd(a, b) , calculado como a / gcd(a, b) × b para que el valor intermedio nunca supere la respuesta. Para 4 y 6 , el mcd es 2 , y 4 / 2 × 6 = 12 .

Q: ¿Cuál es la complejidad temporal de calcular el MCM?

Con la fórmula del MCD, es O(log(min(a, b))) , el costo del algoritmo de Euclides, más una división y una multiplicación. Necesita O(1) de espacio adicional. Buscar entre los múltiplos es mucho más lento: O(min(a, b)) si avanzas de a uno usando el número mayor, y O(lcm(a, b)) si cuentas de uno en uno.

Q: ¿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 ten cuidado con el desbordamiento y usa enteros de 64 bits cuando la lista sea larga.

PrincipianteMatemáticas y simulación

+10

Recibes dos enteros positivos a y b. Devuelve su mínimo común múltiplo: el menor entero positivo que sea divisible por a y b sin dejar resto.

Por ejemplo, los múltiplos de 6 son 6, 12, 18, 24, y así sucesivamente; los múltiplos de 8 son 8, 16, 24, y así sucesivamente, y el primer número que aparece en ambas listas es 24.

Función

lcm(a: integer, b: integer) → integer

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 ≤ 10⁶
1 ≤ b ≤ 10⁶
La respuesta cabe en un entero de 32 bits con signo: lcm(a, b) ≤ 2³¹-1. El producto a × b podría no caber.

Ejemplos

Entrada: a = 4b = 6
Salida: 12
Explicación: Los múltiplos de 6 empiezan por 6, 12, 18; los múltiplos de 4 empiezan por 4, 8, 12. El primer número de ambas listas es 12.

Entrada: a = 7b = 3
Salida: 21
Explicación: 7 y 3 no comparten ningún factor aparte de 1, así que su mínimo común múltiplo es su producto, 21.

Entrada: a = 15b = 45
Salida: 45
Explicación: 15 divide a 45 exactamente, así que 45 ya es múltiplo de ambos, y no existe ningún múltiplo menor de 45.

+15 pruebas ocultas al enviar

Para ir más allá

¿Puedes encontrar el mcd sin usar divisiones ni restos, usando únicamente restas y mitades?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

El mínimo común múltiplo y el máximo común divisor son dos caras de un mismo hecho: gcd(a, b) × lcm(a, b) = a × b. Así que la respuesta rápida es a × b / gcd(a, b), con una salvedad. El producto puede llegar a 10^12, lo que desborda un entero de 32 bits incluso cuando el resultado cabe, así que divides 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 múltiplo de ambos números, así que es al menos tan grande como el mayor de ellos. Empieza con m como candidato en max(a, b) y suma 1 hasta que tanto a como b lo dividan. Pruebas los candidatos en orden creciente, así que el primero que funciona es el menor.

Para 4 y 6 pruebas 6, 7, 8, 9, 10 y 11, que no funcionan, 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 46337 y 46327, dos números primos, la respuesta es 2146654199, así que el bucle se ejecuta más de dos mil millones de veces. Eso es demasiado lento.

Algoritmo

Establece m en el mayor de a y b.
Mientras m % a o m % b no sea 0, suma 1 a m.
Devuelve m.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Avanza en múltiplos del número mayor

Intuición

La mayoría de los candidatos del recuento no sirven: la respuesta tiene que ser un múltiplo del número mayor, al que llamaremos big. Así que pasa directamente de un múltiplo de big al siguiente: big, 2 × big, 3 × big, y detente en el primero que sea divisible por el número menor.

Para 4 y 6, pruebas con 6 (4 no lo divide) y después con 12 (sí lo divide). La respuesta es k × big para algún k, y k es como máximo el número menor, porque small × big siempre es un múltiplo común. Así que el bucle se ejecuta como máximo min(a, b) veces, lo que aquí nunca supera el millón.

Aquí es lo bastante rápido, pero sigue aumentando con la entrada. Con números de hasta 10^18, no lo sería.

Algoritmo

Sea big el número mayor y small el menor.
Establece m = big.
Mientras m % small no sea 0, suma big a m.
Devuelve m.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Divide entre el MCD y después multiplica

Intuición

Descompón ambos números en factores primos. El gcd toma cada primo con la menor de sus dos potencias, el lcm toma la mayor y, juntos, usan cada factor de a y de b exactamente una vez. Así se obtiene gcd(a, b) × lcm(a, b) = a × b, por lo que lcm(a, b) = a × b / gcd(a, b). Para 4 = 2² y 6 = 2 × 3, el gcd es 2 y el lcm es 2² × 3 = 12.

Calcula el gcd con el algoritmo de Euclides: reemplaza (x, y) por (y, x % y) hasta que y sea 0. Eso toma O(log(min(a, b))) pasos.

Después calcula a / gcd × b, en ese orden. El gcd divide a a exactamente, así que la división no pierde nada, y el resultado nunca supera la respuesta. Escribir a × b / gcd en su lugar provoca un desbordamiento de un entero de 32 bits cuando a = b = 10^6: el producto es 10^12, mientras que la respuesta es solo 10^6.

Algoritmo

Copia a y b en x y y.
Mientras y no sea 0, reemplaza (x, y) por (y, x % y). Ahora x es el MCD.
Divide a entre x.
Multiplica el resultado por b y 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

La fórmula es una sola línea, y los errores están en el orden de las operaciones aritméticas.

Calcular primero a × b. En Java, C, C++, C# y Rust, el producto de dos números cercanos a 10^6 desborda un entero de 32 bits y el resultado es incorrecto o negativo (en cambio, una compilación de depuración de Rust provoca un pánico), aunque el mcm verdadero quepa.
Dividir a × b entre el mcd usando números de punto flotante. El resultado puede ser 2.146654199E9 o perder sus últimos dígitos; mantén todo en enteros.
Ejecutar el bucle de Euclides sobre a y b mismos y luego usarlos en la fórmula. Después del bucle, contienen el mcd y 0, así que trabaja con copias.
Suponer que el resultado es a × b. Eso solo se cumple cuando los dos números no comparten factores: lcm(4, 6) es 12, no 24.

Preguntas frecuentes4

¿Cuál es la fórmula del MCM de dos números?

lcm(a, b) = a × b / gcd(a, b), calculado como a / gcd(a, b) × b para que el valor intermedio nunca supere la respuesta. Para 4 y 6, el mcd es 2, y 4 / 2 × 6 = 12.

¿Por qué mcd(a, b) × mcm(a, b) es igual a a × b?

Para cada número primo, el mcd usa la menor de sus potencias en a y b, y el mcm usa la mayor. La menor más la mayor es la suma de ambas potencias, que es exactamente la potencia de ese número primo en a × b. Cada número primo coincide, así que los dos productos son iguales.

¿Cuál es la complejidad temporal de calcular el MCM?

Con la fórmula del MCD, es O(log(min(a, b))), el costo del algoritmo de Euclides, más una división y una multiplicación. Necesita O(1) de espacio adicional. Buscar entre los múltiplos es mucho más lento: O(min(a, b)) si avanzas de a uno usando el número mayor, y O(lcm(a, b)) si cuentas de uno en uno.

¿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 ten cuidado con el desbordamiento y usa enteros de 64 bits cuando la lista sea larga.

Python

def lcm(a, b):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

a = 4
b = 6

Esperado

Least Common Multiple

Función

Restricciones

Ejemplos

Pistas

Solución

Cuenta hacia arriba desde el número mayor

Avanza en múltiplos del número mayor

Divide entre el MCD y después multiplica

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares