Podczas gdy algorytm Euklidesa oblicza tylko największy wspólny dzielnik (GCD) dwóch liczb całkowitych $a$ i $b$, rozszerzona wersja znajduje również sposób na przedstawienie GCD w kategoriach $a$ i $b$, tj. współczynników $x$ i $y$, dla których:

$a ∗ x + b ∗ y = ∗gcd(a, b)$$

Warto zauważyć, że zawsze możemy znaleźć taką reprezentację, na przykład $gcd(55, 80) = 5$ dlatego możemy reprezentować $5$ jako kombinację liniową z członami $55$ i $80$: $55 $ + 80 $ (-2) = 5$

Bardziej ogólna postać tego problemu jest omówiona w artykule o Liniowych równaniach diofantynowych.Będzie on bazował na tym algorytmie.

Algorytm

W tym rozdziale będziemy oznaczać GCD z $a$ i $b$ przez $g$.

Zmiany w oryginalnym algorytmie są bardzo proste.Jeśli przypomnimy sobie algorytm, to zobaczymy, że kończy się on na $b = 0$ i $a = g$.Dla tych parametrów możemy łatwo znaleźć współczynniki, a mianowicie $g = 1 + 0 = g$.

Startując od tych współczynników $(x, y) = (1, 0)$, możemy cofać się w górę wywołań rekurencyjnych.Wszystko, co musimy zrobić, to dowiedzieć się, jak zmieniają się współczynniki $x$ i $y$ podczas przejścia od $(a, b)$ do $(b, a \bmod b)$.

Załóżmy, że znaleźliśmy współczynniki $(x_1, y_1)$ dla $(b, a \bmod b)$:

$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$

i chcemy znaleźć parę $(x, y)$ dla $(a, b)$:

$ a ∗ x + b ∗ y = g$

Możemy przedstawić $a ∗ b$ jako:

$ a ∗ b = a – ∗ lewa ∗ podłoga ∗frac{a}{b} \right \rfloor \cdot b$

Substituting this expression in the coefficient equation of $(x_1, y_1)$ gives:

$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a – \left \frac{a}{b} \bright \rfloor \cdot b \right) \cdot y_1$$

a po ponownym uporządkowaniu wyrażeń:

$g = a ∗ y_1 + b ∗ lewa( x_1 – y_1 ∗ lewa ∗ lewa ∗ prawa ∗ prawa)$$

Znaleźliśmy wartości $x$ i $y$:

$$begin{cases}x = y_1 \}y = x_1 – y_1 \cdot \left \lfloor \frac{a}{b} \right \rfloor \end{cases} $$

Implementacja

int gcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int d = gcd(b, a % b, x1, y1); x = y1; y = x1 - y1 * (a / b); return d;}

Powyższa funkcja rekurencyjna zwraca GCD oraz wartości współczynników do x i y (które są przekazywane przez referencję do funkcji).

Ta implementacja rozszerzonego algorytmu euklidesowego daje poprawne wyniki również dla liczb całkowitych ujemnych.

Wersja iteracyjna

Można również napisać rozszerzony algorytm Euklidesa w sposób iteracyjny.Ponieważ unika się w ten sposób rekurencji, kod będzie działał nieco szybciej niż rekurencyjny.

int gcd(int a, int b, int& x, int& y) { x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1;}

Jeśli przyjrzysz się uważnie zmiennym a1 i b1, możesz zauważyć, że przyjmują one dokładnie takie same wartości jak w iteracyjnej wersji normalnego algorytmu Euklidesa. Zatem algorytm obliczy przynajmniej poprawną GCD.

Aby zobaczyć, dlaczego algorytm oblicza również poprawne współczynniki, można sprawdzić, że w każdej chwili (przed pętlą while i na końcu każdej iteracji) będą zachowane następujące niezmienniki: $x \cdot a + y \cdot b = a_1$ oraz $x_1 \cdot a + y_1 \cdot b = b_1$.Łatwo zauważyć, że te dwa równania są spełnione na początku i można sprawdzić, że aktualizacja w iteracji pętli nadal będzie utrzymywać te równości.

Na końcu wiemy, że $a_1$ zawiera GCD, więc $x \cdot a + y \cdot b = g$.Co oznacza, że znaleźliśmy wymagane współczynniki.

Możesz nawet zoptymalizować kod bardziej, i usunąć zmienne $a_1$ i $b_1$ z kodu, i po prostu ponownie użyć $a$ i $b$.Jeśli jednak tak zrobisz, stracisz możliwość argumentowania o inwariantach.

Problemy praktyczne

• 10104 – Euclid Problem
• GYM – (J) Once Upon A Time
• UVA – 12775 – Gift Dilemma

.