НОД — алгоритм Евклида
После нескольких итераций этого алгоритма становится заметно, что некоторые операции оказываются избыточными, и процесс вычисления наибольшего общего делителя можно оптимизировать.
Если использовать вычитание, мы будем многократно вычитать меньшее число из большего, пока не получим 0 или число, равное НОД. Ускорить это можно, вычисляя остаток от деления большего числа на меньшее. При помощи операции взятия остатка (mod) мы повторно делим большее число на меньшее и берем остаток до тех пор, пока остаток не станет равен 0. Последний ненулевой остаток и будет НОД.
Рассматривайте операцию взятия остатка как более эффективный способ нахождения НОД: вместо многократного вычитания меньшего числа из большего, мы уменьшаем большое число с помощью деления. Фактически, мы поэтапно исключаем общие делители сразу из обоих чисел, поэтому к результату — максимальному общему делителю — мы приходим гораздо быстрее.
a, b = int(input()), int(input())
while a > 0 and b > 0: # Если a или b равно 0, оставшееся число будет НОД
a, b = b, a % b # НОД(a, b) равен НОД(b, a % b)
d = b if a == 0 else a # если a равно 0, значит НОД = b; если b равно 0, значит НОД = a
print('gcd:', d)Этот алгоритм впервые упоминается в книге Евклида, написанной около 300 г. до н. э.
Давайте рассмотрим несколько примеров работы алгоритма:
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ НОД = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ НОД = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ НОД = 1
Входные данные
Единственная строка входных данных содержит два целых числа
a и b (0 ≤ a, b ≤ 10^9).Выходные данные
Программа должна вывести наибольший общий делитель чисел
a и b.Примеры
Входные данные | Выходные данные |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB