Наибольший общий делитель (GCD) при помощи вычитания

Допустим, у нас есть два положительных числа a и b. Нужно найти их наибольший общий делитель (НОД). Однако в этот раз числа могут быть очень большими, поэтому обычный перебор всех делителей и выбор максимального общего из них неэффективен. Необходимо оптимизировать алгоритм.

Предположим, что a > b. Пусть d – это общий делитель, тогда и a, и b делятся на d. То есть:

Таким образом, d является делителем и для a, и для b, а так как x и y – целые числа, то x - y тоже будет целым числом. Следовательно, если a - b = d(x-y), то d должно делить и a-b. Эта идея позволяет сократить количество шагов при поиске НОД.

Если наибольший общий делитель d делит и a, и b, и также a-b, то, чтобы найти d, мы можем воспользоваться тем, что gcd(a, b) = gcd(b, a-b). Таким образом, можем повторять этот процесс, пока одно из чисел не превратится в 0 (в таком случае ненулевое число и есть искомый НОД):

a, b = int(input()), int(input())
while a > 0 and b > 0:  # In case a or b is 0 => the other one is the GCD
    if b > a:           # Let's always keep a >= b
        a, b = b, a     # Swap the numbers
    a, b = a - b, b     # gcd of (a, b) is the same as gcd of (a, b - a)

d = b if a == 0 else a  # if a is 0 => b is GCD, if b is 0 => a is GCD
print('gcd:', d)

Ниже рассмотрим несколько примеров пошагового выполнения этого алгоритма:

Входные данные

В единственной строке входных данных находятся два целых числа a и b (0 ≤ a, b ≤ ).

Выходные данные

Программа должна вывести наибольший общий делитель чисел a и b.

Примеры