F. НОД

В одном из местных НИИ часто требуется находить наибольший общий делитель (НОД) двух чисел.
Вам уже доверяют, как одному из лучших «автоматизаторов» в округе, так что руководство НИИ решило заказать ПО у вас.

Формат ввода

Вводится два натуральных числа, каждое на своей строке.

Формат вывода:

Требуется вывести одно натуральное число — НОД двух данных чисел.

Примечание

Самый распространенный способ поиска НОД — алгоритм Евклида.

Пример

Ввод

12
42

Вывод

6

Ввод

512
625

Вывод

1

Решение

Алгоритм Эвклида изложенный научным языком штука довольно сложная для понимания. К счастью, есть более простые объяснения.
Мы рассмотрим два, наиболее распространных варианта использования этого алгоритма.

Первый заключается в том, чтобы вычитать из большего числа меньшее, пока одно и них не станет равным нулю. Оставшееся ненулевое значение и будет их общим делителем.
Таким образом организуем цикл while() с условием пока a и b не равны нулю.
Если a > b, из a вычитаем b, в противном случае из b вычитаем a.
Когда a или b стали равными нулю печатаем сумму a и b.

Можно слегка ускорить алгоритм, ведь если ввести 99 и 3, то мы вычтем из первого число второе 33 раза. Ускорение сводится к тому, чтобы операцию вычитания заменить на операцию поиска остатка от деления (%). В остальном алгоритм остается тем же.

Существует еще один способ, связанный с поведением оператора % в случае, когда a < b и умением python менять местами две переменных в одной строке. Он показан в третьем варианте решения. Фактически, он является эталонным решением в python.

# Простое решение с вычитанием

a, b = int(input()), int(input())

while a != 0 and b != 0:
    if a >= b:
        a -= b
    else:
        b -= a

print(a + b)

# Ускоренное решение с имспользованием остатка от деления

a, b = int(input()), int(input())

while a != 0 and b != 0:
    if a >= b:
        a %= b
    else:
        b %= a

print(a + b)

# Продвинутое решение с имспользованием остатка от деления

a, b = int(input()), int(input())

while a != 0:
    a, b = b % a, a

print(b)