Algoritmul lui euclid

Pe scurt

Algoritmul lui Euclid calculează cel mai mare divizor comun al două numere întregi a și b. Ideea-cheie: CMMD(a, b) = CMMD(b, a mod b). Repetăm până când restul devine 0.

Intuiție

Dacă împărțim a la b obținem a = q · b + r cu 0 ≤ r < b. Orice divizor comun al lui a și b îl divide și pe r. Deci împărțitorii comuni ai lui a și b sunt exact împărțitorii comuni ai lui b și r. Asta ne permite să micșorăm problema păstrând răspunsul.

Algoritmul (formă cu împărțiri succesive)

1. Dacă b = 0, răspunsul este a (cu semn pozitiv).
2. Înlocuiește (a, b) cu (b, a mod b).
3. Repetă pasul 1.

Pseudocod

func cmmd(a, b):
    a = abs(a); b = abs(b)
    while b != 0:
        (a, b) = (b, a % b)
    return a

Exemplu lucrat

Calculăm CMMD(1071, 462):

1071 = 2 · 462 + 147   → (462, 147)
 462 = 3 · 147 +   21   → (147, 21)
 147 = 7 ·  21 +    0   → (21, 0)  ⇒ CMMD = 21

Implementări

C++

#include 
#include 

long long cmmd(long long a, long long b) {
    a = std::llabs(a); b = std::llabs(b);
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    long long a, b;
    std::cin >> a >> b;
    std::cout << cmmd(a, b) << "\n";
    return 0;
}

Python

def cmmd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

if __name__ == "__main__":
    a, b = map(int, input().split())
    print(cmmd(a, b))

Corectitudine (de ce funcționează)

Avem a = q·b + r. Dacă d divide a și b, atunci divide și diferența a − q·b = r. Reciproc, dacă d divide b și r, atunci divide și a. Deci mulțimea divizorilor comuni ai lui (a, b) este aceeași cu a lui (b, r). Repetând, ajungem la restul 0, iar ultimul divizor nenul este chiar CMMD.

Complexitate

La fiecare pas, al doilea argument scade semnificativ (cel puțin la jumătate după câțiva pași). În practică, numărul de iterații este O(log min(a, b)), ceea ce face algoritmul extrem de eficient.

Varianta extinsă (coeficienții lui Bézout)

Algoritmul extins întoarce, pe lângă CMMD, coeficienți x și y astfel încât ax + by = CMMD(a, b). Util în invers modular și rezolvarea ecuațiilor diofantice.

Pseudocod (iterativ)

func cmmd_extins(a, b):
    a0, b0 = abs(a), abs(b)
    x0, y0 = 1, 0
    x1, y1 = 0, 1
    while b0 != 0:
        q = a0 // b0
        a0, b0 = b0, a0 - q * b0
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return (a0, x0, y0)  # a0 = CMMD

Capcane și bune practici

• Zero: CMMD(a, 0) = |a|, iar CMMD(0, 0) este nedefinit (decide explicit ce returnezi).
• Semn: returnează întotdeauna rezultat pozitiv.
• Overflow: folosește tipuri suficient de mari (long long), însă algoritmul nu face produse mari.
• Date mari: funcționează foarte rapid datorită complexității logaritmice.

Exerciții

1. Calculează manual CMMD(414, 662) arătând toți pașii.
2. Scrie o funcție care întoarce CMMD pentru o listă de numere folosind pliuri succesive.
3. Implementează varianta extinsă și găsește inversul lui 37 modulo 101.
4. Compară numărul de pași pentru perechi aleatoare cu max(a, b) ≤ 10^6.