Задача 76215
|
|
 |
Условие
Дополнить алгоритм предыдущей задачи поиском x и y, для которых ax + by = НОД(a,b).Решение
(Идея сообщена Д. Звонкиным.) Прежде всего заметим, что одновременное деление a и b пополам не меняет искомых x и y. Поэтому можно считать, что с самого начала одно из чисел a и b нечётно. (Это свойство будет сохраняться и далее.) Теперь попытаемся, как и раньше, хранить такие числа p,q,r,s, чтоm = ap + bq,
n = ar + bs.
Проблема в том, что при делении, скажем, m на 2 надо разделить p и q на 2, и они перестанут быть целыми (а станут двоично-рациональными). Двоично-рациональное число естественно хранить в виде пары <числитель, показатель степени двойки в знаменателе>. В итоге мы получаем d в виде комбинации a и b с двоично-рациональными коэффициентами. Иными словами, мы имеем
2id = ax + by
для некоторых целых
x,y и натурального
i.
Что делать, если
i > 1? Если x и y чётны,
то на 2 можно сократить. Если это не так, положение
можно исправить преобразованием
x := x + b,
y := y - a
(оно не меняет ax + by). Убедимся в этом. Напомним, что мы считаем, что одно из чисел a и b нечётно. Пусть это будет a. Если при этом y чётно, то и x должно быть чётным (иначе ax + by будет нечётным). А при нечётном y вычитание из него нечётного a делает y чётным.
