Буратино стал использовать подсказку Пьеро по поиску наибольшего общего делителя для нечетных числел.
Однажды он применил этот способ для чётного и нечётного числа и получил правильный ответ. Буратино выполнив ещё несколько примеров для четного и нечетного числа и понял, что данный алгоритм работает для всех пар чисел, в которых хотя бы одно число нечётное. На уроке он рассказал об этом Мальвине. Мальвина похвалила его, дала мороженое и рассказала о некоторых свойствах НОД (см. теорию).
На основе этих правил Буратино обновил свой алгоритм действий по поиску НОД:
gcd = 1
ПОКА (A чётное ) И (В чётное) ДЕЛАЙ:
А и В делим на 2
gcd умножаем на 2
Находим d=НОД (А. В) (одно из чисел нечётное - для этого случая уже умеем)
Умножаем gcd на d
Промежуточные действия Буратино записывал в тетрадь (смотри примеры)
Напишите программу, которая будет выводить промежуточные результаты работы Буратино.
Входные данные : натуральные чётные
A,
B (числа записаны в две строки, каждое не более 100000)
Выходные данные: Промежуточные записи поиска НОД, аналогичные выводу примеров.
Пояснения:
Первая строка содержит начальное значения чисел
Вторая строка содержит промежуточные значения - числа
C, D и
gcd (хотя бы одно из чисел A,B - нечётное; gcd - степень числа 2)
Третья строка содержит НОД (
C, D)
Четвертая строка содержит НОД (
A, B)
Прмеры промежуточных записей из тетради Буратино:
48
72 |
48 72
6 9 8
3
24 |
768
32 |
768 32
24 1 32
1
32 |
96
36 |
96 36
24 9 4
3
12 |