добавлено: 10 Jun 2008 17:58
редактировано: 17 Oct 2012 14:55

Расширенный алгоритм Евклида

В то время как "обычный" алгоритм Евклида просто находит наибольший общий делитель двух чисел a и b, расширенный алгоритм Евклида находит помимо НОД также коэффициенты x и y такие, что:

a \cdot x + b \cdot y = {\rm gcd} (a, b).

Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

Алгоритм

Внести вычисление этих коэффициентов в алгоритм Евклида несложно, достаточно вывести формулы, по которым они меняются при переходе от пары (a,b) к паре (b\%a,a) (знаком процента мы обозначаем взятие остатка от деления).

Итак, пусть мы нашли решение (x_1,y_1) задачи для новой пары (b\%a,a):

 (b \% a) \cdot x_1 + a \cdot y_1 = g,

и хотим получить решение (x,y) для нашей пары (a,b):

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

Для этого преобразуем величину b \% a:

 b \% a = b - \left\lfloor \frac{b}{a} \right\rflo[...]

Подставим это в приведённое выше выражение с x_1 и y_1 и получим:

 g = (b \% a) \cdot x_1 + a \cdot y_1 = \left( b -[...]

и, выполняя перегруппировку слагаемых, получаем:

 g = b \cdot x_1 + a \cdot \left( y_1 - \left\lflo[...]

Сравнивая это с исходным выражением над неизвестными x и y, получаем требуемые выражения:

 \cases{
x = y_1 - \left\lfloor \frac{b}{a} \righ[...]

Реализация

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

Это рекурсивная функция, которая по-прежнему возвращает значение НОД от чисел a и b, но помимо этого — также искомые коэффициенты x и y в виде параметров функции, передающихся по ссылкам.

База рекурсии — случай a = 0. Тогда НОД равен b, и, очевидно, требуемые коэффициенты x и y равны 0 и 1 соответственно. В остальных случаях работает обычное решение, а коэффициенты пересчитываются по вышеописанным формулам.

Расширенный алгоритм Евклида в такой реализации работает корректно даже для отрицательных чисел.

Литература

 

 


powered by e-maxx.ru