Cel mai mic multiplu comun

Cel mai mic multiplu comun pozitiv al două întregi pozitive este cel mai mic număr pozitiv divizibil cu amândouă. Pentru 12 și 18, multiplii comuni încep cu 36, deci $\mathrm{cmmmc}(12,18)=36$. Folosim relația $\mathrm{cmmmc}(a,b)=a\cdot b/\mathrm{cmmdc}(a,b)$, după calcularea CMMDC prin algoritmul lui Euclid.

Cel mai mic multiplu comun al numerelor naturale nenule $a$ și $b$ se obține din identitatea $\mathrm{cmmdc}(a,b)\cdot \mathrm{cmmmc}(a,b)=a\cdot b$. Pentru $a=12$ și $b=18$, $\mathrm{cmmdc}=6$ și $\mathrm{cmmmc}=12\cdot 18/6=36$. Se calculează cmmdc cu algoritmul lui Euclid, apoi se împarte unul dintre numere la cmmdc înainte de înmulțire: expresia a / cmmdc * b nu depășește tipul întreg dacă rezultatul încape în el, pe când produsul $a\cdot b$ ar putea să-l depășească.

Exemplul 1 — $\mathrm{cmmmc}(12;18)$.

1. Euclid pentru $(12;18)$: $(12;18)\to (18;12)\to (12;6)\to (6;0)$, deci cmmdc este 6.
2. Se împarte $12/6=2$.
3. Se înmulțește $2\cdot 18=36$.

#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 main() {
    int a = 12, b = 18;
    cout << a / cmmdc(a, b) * b;
    return 0;
}

Programul afișează 36.

Exemplul 2 — trei numere. Pentru $4$, $6$ și $10$ se aplică formula de două ori: $\mathrm{cmmmc}(4;6)=12$, apoi $\mathrm{cmmmc}(12;10)=60$. Rezultatul 60 este cel mai mic număr divizibil cu toate trei. O problemă tipică: două becuri se aprind la intervale de 12 s și de 18 s și s-au aprins simultan la momentul 0; următoarea aprindere simultană are loc după $\mathrm{cmmmc}(12;18)=36$ s.

Exemplul 3 — legătura cu descompunerea în factori primi. Din $12=2^2\cdot 3$ și $18=2\cdot 3^2$ rezultă că $\mathrm{cmmdc}(12;18)=2^1\cdot 3^1=6$ (puterile cele mai mici ale factorilor comuni) și $\mathrm{cmmmc}(12;18)=2^2\cdot 3^2=36$ (puterile cele mai mari ale tuturor factorilor). Dacă $\mathrm{cmmdc}(a;b)=1$, numerele sunt prime între ele și $\mathrm{cmmmc}(a;b)=a\cdot b$; de pildă $\mathrm{cmmmc}(8;15)=120$. Același cmmmc apare la adunarea fracțiilor: numitorul comun al fracțiilor $\frac{5}{12}$ și $\frac{7}{18}$ este 36, iar suma este $\frac{15+14}{36}=\frac{29}{36}$.

Rezultatul este cel puțin cel mai mare dintre numere și cel mult produsul lor: pentru 12 și 18 el se află între 18 și 216, iar valoarea 36 este un multiplu al fiecăruia. Formula se justifică simplu. Dacă $g=\mathrm{cmmdc}(a;b)$, atunci $a=g\cdot a^{\prime }$ și $b=g\cdot b^{\prime }$, cu $a^{\prime }$ și $b^{\prime }$ prime între ele. Cel mai mic număr divizibil cu ambele este $g\cdot a^{\prime }\cdot b^{\prime }$, iar acesta este egal cu $a\cdot b/g$. Pentru șirul $1,2,\dots ,10$ se aplică formula pas cu pas: cmmmc crește la 2, 6, 12, 60, 60, 420, 840, 2520, 2520, deci cel mai mic număr divizibil cu toate cifrele nenule este 2520.

Algoritmul nu caută multiplii unul câte unul. O căutare ar testa multiplii lui $a$ până la primul divizibil cu $b$, adică până la $b/\mathrm{cmmdc}(a;b)$ multipli, iar formula cu Euclid ajunge la același rezultat în $O(\log \min (a,b))$ pași.

Exemplul 4 — cmmmc al unui șir. Pentru $6,8,15$ păstrăm în m multiplul comun parțial. Pornim cu m = 6. Pentru 8: cmmdc este 2, deci m = 6 / 2 * 8 = 24. Pentru 15: cmmdc este 3, deci m = 24 / 3 * 15 = 120. Dacă un număr îl divide pe celălalt, cmmmc este cel mai mare dintre ele: pentru 6 și 18, cmmdc este 6 și cmmmc este 18.

Atenție la nule: dacă unul dintre numere este 0, formula ar împărți la cmmdc, care poate fi nul pentru $a=b=0$. Convenția $\mathrm{cmmmc}(a;0)=0$ se aplică numai dacă enunțul o cere.

Pentru $a,b>0$ folosește $\mathrm{cmmmc}(a;b)=\frac{a}{\mathrm{cmmdc}(a;b)}\cdot b$. Împărțirea înainte de înmulțire reduce riscul de depășire a tipului. Cmmdc se calculează cu algoritmul lui Euclid, fără funcții de bibliotecă; același cod se scrie în C sau în C++.

#include <iostream>
using namespace std;
int main() {
    long long a, b, x, y;
    cin >> a >> b;
    x = a; y = b;
    while (y != 0) {
        long long r = x % y;
        x = y; y = r;
    }
    long long c = (a == 0 || b == 0) ? 0 : (a / x) * b;
    cout << c;
}

Pentru $a=18$ și $b=24$ resturile duc la $\mathrm{cmmdc}=6$, apoi $c=(18/6)\cdot 24=72$. Complexitatea algoritmului lui Euclid este $O(\log \min (a,b))$ pentru valori pozitive.

Ordinea operațiilor decide corectitudinea la limita tipului int. Pentru $a=60000$ și $b=50000$, produsul $a\cdot b=3000000000$ depășește $2147483647$, deși $\mathrm{cmmdc}=10000$ și $\mathrm{cmmmc}=300000$ încap ușor. Expresia a / cmmdc * b calculează $6\cdot 50000=300000$, pe când a * b / cmmdc depășește tipul înainte de împărțire și produce o valoare greșită.

Exemplul 2 — număr de multipli comuni. Câte numere din intervalul $[1;100]$ se divid atât cu 4, cât și cu 6? Un număr se divide cu amândouă exact când se divide cu $\mathrm{cmmmc}(4;6)=12$, nu cu produsul 24. Multiplii lui 12 din interval sunt 12, 24, …, 96, adică $\lfloor 100/12\rfloor =8$ numere. Greșeala tipică este să numeri multiplii lui 24 și să obții 4.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int a = 20, b = 30, x = a, y = b;
while (y != 0) {
    int r = x % y;
    x = y;
    y = r;
}
cout << a / x * b;

• a) 10
• b) 30
• c) 60
• d) 600

Răspunsul corect este c). Ciclul calculează cmmdc: $(20;30)\to (30;20)\to (20;10)\to (10;0)$, deci $x=10$. Se afișează $20/10\cdot 30=60$. Varianta d) este produsul $20\cdot 30$, adică valoarea obținută fără împărțirea la cmmdc, iar varianta a) este chiar cmmdc.

Greșeli frecvente

• Greșit: CMMMC al lui 12 și 18 este 216, produsul lor.
  Corect: împărțim produsul la CMMDC și obținem 36.
• Greșit: calculez întâi $a\cdot b$ și apoi împart la CMMDC.
  Corect: împart întâi a la CMMDC, apoi înmulțesc cu b, ca produsul intermediar să fie mai mic.
• Greșit: formula cu CMMDC se poate folosi fără precizări pentru $a=b=0$.
  Corect: numitorul devine zero și cazul cere tratare separată.

Înainte și după