Изменения

Перейти к: навигация, поиск

Наибольший общий делитель

7 байт добавлено, 16:30, 17 мая 2018
Расширенный алгоритм Евклида
===Расширенный алгоритм Евклида===
В стандартном алгоритме, мы использовали следующее свойство: <tex>\gcd(a, b) = \gcd(b, a \bmod b)</tex>. Воспользуемся им для того, чтобы решить следующую задачу: найти <tex>x</tex> и <tex>y</tex> такие, что <tex>a \cdot x + b \cdot y = \gcd(a, b)</tex>. Пусть мы нашли пару <tex>x_1, y_1: \: b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(a, b)</tex>.
Очевидно, что <tex>a \bmod b = a - \lfloor \dfrac{a}{b}\rfloor \cdot b</tex>. Получаем: <tex>b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - \lfloor \dfrac{a}{b}\rfloor \cdot b\right) \cdot y_1 =
b \cdot \left(x_1 - \lfloor \dfrac{a}{b}\rfloor \cdot y_1\right) + a \cdot y_1</tex>. Следовательно, приходим к расширенному алгоритму Евклида:
<font color="green">// Алгоритм возвращает тройку <tex>\gcd, x, y</tex></font>
344
правки

Навигация