Cel mai mare divizor comun

Algoritmul lui Euclid prin scăderi și prin restul împărțirii, cmmmc-ul care se deduce din el și fracțiile ireductibile.

Problema

Cmmdc-ul a două numere este cel mai mare număr care le divide pe amândouă. Pentru 84 și 36, divizorii comuni sunt 1, 2, 3, 4, 6, 12, deci cmmdc este 12.

L-ai putea căuta încercând toate numerele de la minim în jos. Ar merge, dar face până la min(a,b) pași. Există o metodă mult mai bună, cunoscută de vreo două mii de ani.

Ideea

Dacă un număr divide și pe a, și pe b, atunci divide și diferența lor. Prin urmare perechea (a, b) și perechea (a-b, b) au exact aceiași divizori comuni, deci și același cmmdc.

Asta înseamnă că poți înlocui numărul mai mare cu diferența de câte ori vrei, fără să schimbi răspunsul. Numerele scad, iar când devin egale, ai ajuns la răspuns.

Prin scăderi repetate

while (a != b) {
    if (a > b) a = a - b;
    else b = b - a;
}
cout << a;

Pentru 84 și 36:

Răspunsul este 12.

Varianta aceasta apare des la Subiectul I, pentru că se urmărește ușor pe hârtie. Are însă un defect: pentru 1000000 și 1 face un milion de pași.

Prin restul împărțirii

Dacă îl scazi pe b din a de câte ori se poate, rămâi exact cu a % b. Deci:

while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
}
cout << a;

Pentru 84 și 36:

Ai două împărțiri în loc de patru scăderi. La numere mari diferența devine uriașă: chiar și pentru numere de ordinul miliardelor, algoritmul se termină în cel mult câteva zeci de pași.

Răspunsul este a după buclă, când b a devenit 0. O greșeală frecventă este să afișezi b, care este întotdeauna 0.

Cazurile limită se rezolvă singure. Dacă b este 0 de la început, răspunsul este a, și e corect, pentru că orice număr divide pe 0.

Ca funcție

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

Parametrii sunt transmiși prin valoare, deci numerele originale nu se modifică. Este forma pe care ar trebui s-o poți scrie din reflex.

Cel mai mic multiplu comun

Nu are nevoie de un algoritm separat. Există relația:

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

Deci:

long long cmmmc = 1LL * a / cmmdc(a, b) * b;

Observă două lucruri.

Împarte înainte să înmulțești. a * b poate depăși tipul chiar dacă rezultatul final încape. Dacă împarți întâi la cmmdc, care sigur divide pe a, eviți depășirea fără să pierzi precizie.

Prefixul 1LL forțează calculul pe long long, cum am văzut la tipuri de date.

Pentru mai multe numere

Calculezi cmmdc-ul pe rând, acumulând:

int d = 0;
for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    d = cmmdc(d, x);
}
cout << d;

Trucul este inițializarea cu 0. Cum cmmdc(0, x) este x, prima valoare intră corect fără caz special. Pentru cmmmc inițializezi cu 1.

Fracții ireductibile

O aplicație directă: simplifici o fracție împărțind numărătorul și numitorul la cmmdc-ul lor.

int d = cmmdc(a, b);
cout << a / d << "/" << b / d;

Ca să aduni două fracții, le aduci la același numitor și simplifici la final:

// a/b + c/d
int numarator = a * d + c * b;
int numitor = b * d;
int g = cmmdc(numarator, numitor);
cout << numarator / g << "/" << numitor / g;

De reținut

• Cmmdc-ul nu se schimbă dacă înlocuiești numărul mare cu diferența. Pe asta se bazează tot algoritmul.
• Varianta cu % este mult mai rapidă decât cea cu scăderi.
• Răspunsul este a când b a ajuns 0.
• cmmmc = a / cmmdc * b, cu împărțirea înaintea înmulțirii.
• Pentru un șir de numere, acumulează pornind de la 0 (cmmdc) sau de la 1 (cmmmc).