Zatímco euklidovský algoritmus počítá pouze největšího společného dělitele (GCD) dvou celých čísel $a$ a $b$, rozšířená verze najde také způsob, jak reprezentovat GCD v termínech $a$ a $b$, tj. koeficientů $x$ a $y$, pro které:

$$a \cdot x + b \cdot y = \gcd(a, b)$$

Je důležité poznamenat, že takovou reprezentaci můžeme najít vždy, například $\gcd(55, 80) = 5$, proto můžeme 5$ reprezentovat jako lineární kombinaci s členy $55$ a $80$: Obecnější podoba tohoto problému je popsána v článku o lineárních diofantovských rovnicích: $55 \cdot 3 + 80 \cdot (-2) = 5$

.Bude vycházet z tohoto algoritmu.

Algoritmus

V této části budeme označovat GCD $a$ a $b$ pomocí $g$.

Změny oproti původnímu algoritmu jsou velmi jednoduché. připomeneme-li si algoritmus, vidíme, že algoritmus končí hodnotami $b = 0$ a $a = g$. pro tyto parametry můžeme snadno najít koeficienty, a to $g \cdot 1 + 0 \cdot 0 = g$.

Vycházíme-li z těchto koeficientů $(x, y) = (1, 0)$, můžeme jít zpětně po rekurzivních voláních.Stačí zjistit, jak se mění koeficienty $x$ a $y$ při přechodu z $(a, b)$ na $(b, a \bmod b)$.

Předpokládejme, že jsme našli koeficienty $(x_1, y_1)$ pro $(b, a \bmod b)$:

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

a chceme najít dvojici $(x, y)$ pro $(a, b)$:

$$ a \cdot x + b \cdot y = g$$

Můžeme reprezentovat $a \bmod b$ jako:

$$ a \bmod b = a – \left\lfloor \frac{a}{b} \pravá\rfloor \cdot b$$

Při dosazení tohoto výrazu do rovnice koeficientu $(x_1, y_1)$ dostaneme:

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

a po přeskupení členů:

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

Zjistili jsme hodnoty $x$ a $y$:

$$\begin{cases}x = y_1 \\y = x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \pravý\rfloor\konec{případů} $$

Implementace

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;}

Výše uvedená rekurzivní funkce vrací GCD a hodnoty koeficientů x a y (které jsou funkci předány odkazem).

Tato implementace rozšířeného Euklidova algoritmu dává správné výsledky i pro záporná celá čísla.

Iterativní verze

Rozšířený euklidovský algoritmus je možné zapsat také iterativním způsobem. protože se vyhne rekurzi, bude kód běžet o něco rychleji než rekurzivní.

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;}

Podíváte-li se pozorně na proměnné a1 a b1, můžete si všimnout, že nabývají přesně stejných hodnot jako v iterativní verzi normálního euklidovského algoritmu. Algoritmus tedy alespoň vypočítá správný GCD.

Chcete-li zjistit, proč algoritmus vypočítá i správné koeficienty, můžete se přesvědčit, že v každém okamžiku (před cyklem while a na konci každé iterace) budou platit následující invarianty: $x \cdot a + y \cdot b = a_1$ a $x_1 \cdot a + y_1 \cdot b = b_1$.Je triviální se přesvědčit, že tyto dvě rovnice jsou na začátku splněny, a můžete zkontrolovat, že aktualizace v iterační smyčce stále zachovává platnost těchto rovností.

Na konci víme, že $a_1$ obsahuje GCD, takže $x \cdot a + y \cdot b = g$. což znamená, že jsme našli požadované koeficienty.

Kód můžete ještě více optimalizovat a odstranit z něj proměnné $a_1$ a $b_1$ a pouze znovu použít $a$ a $b$.Pokud to však uděláte, ztratíte možnost argumentovat invarianty.

Praktické úlohy

• 10104 – Euklidův problém
• GYM – (J) Bylo nebylo
• UVA – 12775 – Dárkové dilema

.