ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76215
Темы:    [ Знакомство с циклами ]
[ Задачи с целыми числами ]
[ НОД и НОК. Алгоритм Евклида ]
Сложность: 3+
Классы:
В корзину
Прислать комментарий

Условие

Дополнить алгоритм предыдущей задачи поиском 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 чётным.

Источники и прецеденты использования

книга
Автор А.Шень
Название Программирование: теоремы и задачи
Издательство МЦНМО
Издание второе
Год издания 2004
глава
Номер 1
Название Переменные, выражения, присваивания
параграф
Номер 1
Название Задачи без массивов
задача
Номер 1.1.19

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .