Алгоритмы и структуры данных

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

Допустим, у нас есть два положительных числа a и b. Нужно найти их наибольший общий делитель (НОД). Однако в этот раз числа могут быть очень большими, поэтому обычный перебор всех делителей и выбор максимального общего из них неэффективен. Необходимо оптимизировать алгоритм.
Предположим, что a > b. Пусть d – это общий делитель, тогда и a, и b делятся на d. То есть:
где x и y – некоторые целые числа. Если мы вычтем b из a, получим:
 
Таким образом, 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 = 8, b = 12
  1. b > a ⇒ swap ⇒ a = 12, b = 8 a = 12 - 8 = 4, b = 8
  1. b > a ⇒ swap ⇒ a = 8, b = 4 a = 8 - 4 = 4, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. break ⇒ GCD = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. b > a ⇒ swap ⇒ a = 24, b = 6 a = 24 - 6 = 18, b = 6
  1. a = 18 - 6 = 12, b = 6
  1. a = 12 - 6 = 6, b = 6
  1. a = 6 - 6 = 0, b = 6
  1. break ⇒ GCD = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. b > a ⇒ swap ⇒ a = 16, b = 1 a = 16 - 1 = 15, b = 1
  1. a = 14, b = 1
  1. a = 13, b = 1
  1. a = 12, b = 1
  1. …
  1. …
  1. a = 0, b = 1
  1. break ⇒ GCD = 1

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

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

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

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

Примеры

Input
Output
8 12
4
54 24
6
17 16
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue