Пьеро увидел как Буратино "мучается" с домашним заданием Мальвины по поиску наибольшего общиего делителя двух натуральных чисел с помощью простого Алгоритма Евклида.
Пьеро решил помочь Буратино и показал ему как можно "ускорить" поиск НОДа, если оба числа нечётные.
Пьеро спешил на встречу с Мальвиной, поэтому некоторые операции проводил "в уме" (объясняя Буратино свои действия).
Попробуйте понять и воспроизвести алгоритм Пьеро на основе следующих примеров.
Примеры решений Пьеро по поиску НОД для нечётных чисел :
| входные данные |
выходные данные |
33
45 |
33 45
33 3
15 3
3 3
3 |
45
21 |
45 21
3 21
3 9
3 3
3 |
1625
45 |
1625 45
395 45
175 45
65 45
5 45
5 5
5 |
1045
21 |
1045 21
1 21
1 |
Напишите программу, реализующую данный алгоритм.
Входные данные : Натуральные нечётные числа
A,
B (числа записаны в две строки, каждое не более 10001). Гарантируется, что
А не равно
В.
Выходные данные: Полная запись решения (набор строк, в каждой результат очередного действия, смотри примеры). В последней строке указано одно число - НОД