De ce contează?
Două trenuri pleacă din aceeași gară: unul la fiecare 4 minute, celălalt la fiecare 6 minute. Când se vor întâlni din nou? La minutul 12 — cel mai mic multiplu comun. CMMMC apare ori de câte ori sincronizezi cicluri sau găsești numitorul comun al unor fracții.
Ce este CMMMC?
Cel Mai Mic Multiplu Comun al lui a și b este cel mai mic număr pozitiv care este multiplu al ambelor.
Relația fundamentală:
CMMMC(a, b) = a × b / CMMDC(a, b)Exemplu: CMMMC(4, 6) = 4 × 6 / CMMDC(4, 6) = 24 / 2 = 12
De ce funcționează formula?
Produsul a × b conține toți factorii ambelor numere, dar factorii comuni apar de două ori. Împărțind la CMMDC — care este produsul factorilor comuni — eliminăm duplicatele și obținem exact ce avem nevoie.
Implementare C++
#include <iostream>
using namespace std;
int cmmdc(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int cmmmc(int a, int b) {
return (a / cmmdc(a, b)) * b; // impartim intai pentru a evita overflow
}
int main() {
int a, b;
cin >> a >> b;
cout << "CMMMC(" << a << ", " << b << ") = " << cmmmc(a, b) << endl;
return 0;
}Exemplu: Input 4 6 → CMMMC(4, 6) = 12
Formula (a / cmmdc) * b împarte mai întâi, reducând riscul de overflow. Varianta a * b / cmmdc calculează produsul înainte de împărțire: pentru a = b = 100.000, a * b = 10¹⁰ depășește int și chiar long long-ul util. Ordinea operațiilor contează.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| CMMMC via CMMDC | O(log(min(a,b))) | O(1) |
Greșeala 1: Scrii a * b / cmmdc(a, b) — produsul a * b poate da overflow la int chiar pentru valori moderate. Formula sigură: (a / cmmdc(a, b)) * b.
Greșeala 2: Confunzi CMMDC cu CMMMC. CMMDC ≤ min(a, b); CMMMC ≥ max(a, b). Dacă rezultatul tău e mai mic decât ambele numere, ai calculat CMMDC în loc de CMMMC.
Greșeala 3: CMMMC cu zero este nedefinit (sau 0 prin convenție). Verifică că inputul este pozitiv înainte de apel.