Medio · teoría de números

Mínimo común múltiplo

Ya tienes gcd de Máximo común divisor. El MCM es solo a / gcd(a,b) * b — pero el orden importa, o el producto se desborda.

En una fraseEl MCM es a / gcd(a, b) * b: divide antes de multiplicar; con 10⁴ el producto aún cabría, pero ese hábito es lo que lo mantiene correcto cuando las entradas crecen.

El problema

Entrada: dos líneas, cada una con un entero: a y luego b (1 ≤ a, b ≤ 10000).

Salida: su mínimo común múltiplo.

Ejemplos:

EntradaSalida
4
6		12
3
5		15
12
18		36

Tu solución

main.cpp — tu solución
Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — la fórmula

mcm(a,b) = a * b / mcd(a,b). Pero escríbelo como a / mcd(a,b) * b — dividir primero mantiene pequeño el valor intermedio, así no desborda un int de 32 bits en estos rangos.

Pista 2 — números iguales

Si a == b, la respuesta es simplemente a — y la fórmula también la da, sin caso especial. Ojo con el orden: a / mcd * b es aritmética entera, así que divide antes de multiplicar.

Solución (¡inténtalo primero!) 
#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a / gcd(a, b) * b << endl;
    return 0;
}

Ahora puedes escalar: cuántos múltiplos de k caben entre dos límites, o simplificar una fracción con mcd y luego encontrar un denominador común con mcm. Siguiente: Número de Armstrong.

Análisis profundo

Por qué funciona

La identidad a * b = mcd(a,b) * mcm(a,b) es todo el truco: con el MCD, el MCM queda a una división de distancia. Sin recorrer múltiplos ni adivinar.

El coste

O(log min(a,b)) de tiempo, igual que el MCD de Euclides. O(1) de espacio. El orden a / mcd * b mantiene el intermedio dentro de 32 bits para estas entradas.

Dónde falla

  • Escribir a * b / mcd(a,b) multiplica primero; con a y b grandes ese intermedio desborda el int y la respuesta sale negativa.
  • Si en el MCD inviertes el orden a = b; b = a % b sin guardar antes el resto, puedes entrar en bucle infinito o devolver 0.

Siguiente paso

La misma función con otro uso: simplificar una fracción dividiendo ambos términos por el MCD. Número de Armstrong da la vuelta a la idea de dígitos y potencias.

Dos cosas para recordar

  • mcm(a,b) = a / mcd(a,b) * b — divide antes de multiplicar.
  • El MCD de Euclides es la herramienta reutilizable; casi todo problema de números está a una llamada de distancia.
🐞 Esta versión falla: ábrela y pruébala

Imprime el producto y no el MCM: 4 6 da 24 y el juez quiere 12

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a * b << endl;   // product, not lcm
    return 0;
}