CMMMC — AlgoClar

De ce contează?

Doi prieteni vizitează biblioteca: unul o dată la 4 zile, celălalt o dată la 6 zile. Peste câte zile se întâlnesc din nou acolo? Peste 12 — cel mai mic număr divizibil și cu 4, și cu 6. Acesta este cel mai mic multiplu comun.

Ce este CMMMC

CMMMC(a, b) (cel mai mic multiplu comun) este cel mai mic număr divizibil și cu a, și cu b. Exemplu: cmmmc(4, 6) = 12.

Legătura cu CMMDC

Există o formulă elegantă care leagă cele două:

cmmmc(a, b) = a · b / cmmdc(a, b)

Intuiție: produsul a · b numără factorii comuni de două ori; împărțind la cmmdc scoatem duplicatul și rămâne cel mai mic multiplu.

Algoritm pas cu pas: cmmmc(12, 18)

cmmdc(12, 18) = 6.
cmmmc = 12 · 18 / 6 = 216 / 6 = 36.

Verificare: 36 = 3·12 = 2·18 → divizibil cu ambele. Niciun număr mai mic nu are proprietatea.

Implementare C++

#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    while (b != 0) {
        int rest = a % b;
        a = b;
        b = rest;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;
    long long rez = (long long)a / cmmdc(a, b) * b;   // impartim inainte de inmultire
    cout << rez << "\n";   // 12 18 -> 36
    return 0;
}

Observația-cheie

Ordinea a / cmmdc(a, b) * b nu e întâmplătoare. cmmdc(a, b) divide exact pe a, deci împărțirea e fără rest, iar produsul rămâne mic. Scris invers, a * b s-ar putea sparge înainte de împărțire.

De ce overflow e pericolul principal

Pentru a = b = 100000, a * b = 10¹⁰ — depășește int (limita ~2,1 miliarde). Chiar și cu long long, dacă valorile sunt mari, împărțirea înainte de înmulțire ține numerele sub control.

Complexitate

Caz	Timp	Spațiu
oricare	O(log(min(a, b)))	O(1)

Tot costul vine din cmmdc (Euclid); formula în sine e O(1).

Greșeli frecvente

Capcane reale la CMMMC:

Overflow la a * b: produsul a două numere de ordinul 10⁵ se sparge în int. Folosește long long și împarte înainte de înmulțire.
Împărțire la cmmdc greșit calculat: dacă cmmdc dă 0 (când ambele sunt 0), împarți la 0. Tratează cazul a = b = 0 separat.
Ordinea a * b / cmmdc: corectă matematic, dar riscantă numeric. Preferă a / cmmdc * b.
Confuzi cmmmc cu cmmdc: cmmmc e cel mai mic multiplu, cmmdc e cel mai mare divizor — produsul lor e a · b.

De reținut

cmmmc(a, b) = a · b / cmmdc(a, b).
Scrie a / cmmdc(a, b) * b în long long ca să eviți overflow-ul.
Tot efortul e în cmmdc (Euclid, O(log)); formula e O(1).