10104. Задача Евклида
Со времен Евклида известно, что
для любых положительных a и b существуют такие целые x и y, что ax + by = d, где d – наибольший общий делитель a и b. По заданным a и b найти x, y, d.
Вход.
Каждая строка содержит два числа a и
b, разделенных пробелом (a, b £ 109).
Выход. Для
каждого теста вывести три числа x, y, d, разделенных пробелом. Если
существует несколько пар x и y, то вывести ту пару, для которой x £ y
и выражение |x| + |y| минимально.
Пример входа
4 617 175 3
Пример выхода
-1 1 20 1 17-1 2 1
РЕШЕНИЕ
наибольший общий делитель
Анализ алгоритма
Пусть
для положительных целых чисел a и b (a > b) известно g = НСД(b, a mod b), а также числа x’ и y’, для которых
g = x’ * b + y’ * (a
mod b)
Поскольку
a mod b = a - 
* b, то
g = x’ * b + y’ * (a
- * b) = y’
* a + (x’ - y’
* ) * b = x * a + y * b,
где
обозначено x = y’, y = x’ -
y’ * .
Пусть gcdext(int a, int b, int *d, int *x, int *y) – функция, которая по входным числам a и b находит d = НСД(a, b) и такие x, y что d = a * x + b * y. Для
поиска неизвестных x и y необходимо
рекурсивно запустить функцию gcdext(b, a
mod b, d, x, y)
и пересчитать значения x и y по выше приведенной формуле. Рекурсия заканчивается, когда b =
0. При b = 0 НОД(a, 0) = a и a = a * 1 + 0
* 0, поэтому полагаем x = 1, y
= 0.
Пример
Рассмотрим третий тест.
Вычисление НОД(5, 3) и нахождение соответствующих x,
y произведем
в таблице:
|
a |
b |
x |
y |
|
5 |
3 |
-1 |
2 |
|
3 |
2 |
1 |
-1 |
|
2 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
Из таблицы находим, что НОД(5, 3)
= 5 * (-1) + 3 * 2 = 1.
Реализация алгоритма
Приведем функцию gcdext, которая вычисляет x, y, d по расширенному алгоритму Евклида.
void gcdext(int
a,int b, int
*d, int *x, int
*y)
{
int s;
if (b == 0)
{
*d = a; *x = 1; *y = 0;
return;
}
gcdext(b,a % b,d,x,y);
s = *y;
*y = *x - (a / b) * (*y);
*x = s;
}
Для решения задачи достаточно
прочитать входные данные, вызвать функцию gcdext и напечатать результат.
while(scanf("%d
%d",&a,&b) == 2)
{
gcdext(a,b,&d,&x,&y);
printf("%d %d
%d\n",x,y,d);
}