CMMDC și CMMMC: algoritmul lui Euclid în C++

CMMDC este cel mai mare divizor comun a două numere, iar CMMMC este cel mai mic multiplu comun pozitiv atunci când ambele numere sunt pozitive. Algoritmul lui Euclid calculează CMMDC înlocuind repetat perechea (a,b) cu (b,a%b), până când al doilea număr devine zero.

Nu trebuie să enumeri toți divizorii și nici toți multiplii. Ideea importantă este că o transformare mică păstrează mulțimea divizorilor comuni și reduce dimensiunea problemei.

Cum funcționează

Dacă a=qb+r, orice număr care divide a și b divide și r=a-qb. Invers, un număr care divide b și r divide și a=q*b+r. Prin urmare, CMMDC(a,b)=CMMDC(b,r). Restul este mai mic decât b, astfel încât repetarea se oprește.

Când b=0, rezultatul este a. Pentru numere nenegative folosim convenția CMMDC(0,b)=b și CMMDC(0,0)=0. Aceasta simplifică funcția, dar trebuie să explicăm că perechea (0,0) este tratată prin convenție, nu prin existența unui cel mai mare divizor pozitiv al lui zero.

Pentru numere pozitive, relația CMMDC(a,b)CMMMC(a,b)=ab permite calcularea multiplului comun. Împărțim mai întâi a la CMMDC și apoi înmulțim cu b, ca să reducem riscul depășirii tipului. Reordonarea nu garantează că rezultatul final încape pentru orice intrare. Programul presupune 0 <= a,b <= 1000000000, astfel încât produsul maxim încape în long long.

Exemplu urmărit pas cu pas

Pentru 84 și 30, resturile sunt 24, 6 și 0. Perechile succesive sunt (84,30), (30,24), (24,6), (6,0), deci CMMDC este 6. CMMMC este 84/6*30=420.

Dacă inversezi intrarea, prima iterație poate doar să inverseze rolurile numerelor, dar rezultatul rămâne același. Perechea (0,18) devine (18,0) și produce 18; CMMMC este definit aici ca zero când unul dintre numere este zero.

Implementare C++17

#include <iostream>
long long gcd(long long a, long long b) {
    while (b) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main() {
    long long a, b;
    std::cin >> a >> b;
    long long d = gcd(a, b);
    std::cout << d << ' ' << (a == 0 || b == 0 ? 0 : a / d * b) << '\n';
}

De ce funcționează și cât costă

Mulțimea divizorilor comuni rămâne neschimbată după fiecare transformare. La final, divizorii comuni ai lui a și zero sunt divizorii lui a, iar maximul lor este a pentru a pozitiv. Acesta este invariantul care justifică rezultatul.

Numărul împărțirilor este O(log(min(a,b))) pentru intrări pozitive, iar memoria este O(1) în varianta iterativă. Valorile consecutive din șirul Fibonacci produc multe dintre cazurile dificile, însă algoritmul rămâne foarte rapid.

Greșeli frecvente

Nu efectua a%b atunci când b este zero. Nu calcula CMMMC prin a*b/d într-un tip prea mic. Pentru intrări negative trebuie stabilită normalizarea semnului, inclusiv tratamentul celei mai mici valori reprezentabile; exemplul se limitează explicit la numere nenegative.

Exersează

Calculează CMMDC și CMMMC pentru 18 și 24. Apoi explică de ce 8 și 9 sunt prime între ele.

Rezolvare explicată: Euclid produce resturile 18,6,0 pentru perechea (18,24), deci CMMDC=6 și CMMMC=72. Pentru 8 și 9, ultimul rest nenul este unu, chiar dacă nici 8, nici 9 nu sunt numere prime.

Continuă să înveți

Divizibilitate, funcții și operatorul rest.

Întrebări frecvente

De ce folosim restul în algoritmul lui Euclid?

Perechile (a,b) și (b,a%b) au aceiași divizori comuni. Restul reduce problema fără să schimbe rezultatul căutat.

Trebuie să fie a mai mare decât b?

Nu. Dacă a este mai mic, prima transformare schimbă practic ordinea numerelor. Bucla standard funcționează pentru ambele ordini.

Cum calculez CMMMC fără să caut multipli?

Calculezi mai întâi CMMDC, apoi a/CMMDC*b pentru numere pozitive. Verifici separat cazul cu zero și limitele tipului numeric.

Ce înseamnă numere prime între ele?

Două numere sunt prime între ele dacă CMMDC este unu. Nu este necesar ca fiecare dintre cele două numere să fie prim.

Cum calculez CMMDC pentru mai multe numere?

Aplici funcția succesiv: rezultatul primelor două se combină cu al treilea și așa mai departe. Poți inițializa acumulatorul cu zero pentru numere nenegative.