Разбор задачи «Наибольший общий делитель»

1. Идея

Нужно найти наибольший общий делитель чисел a и b, то есть самое большое число, которое делит оба без остатка.

Для этого в условии уже дан правильный способ — алгоритм Евклида:

• пока b не равно 0, заменяем пару (a, b) на (b, a mod b);
• когда b становится равным 0, ответом будет текущее a.

Именно этот алгоритм и нужно реализовать.

2. Наблюдения

Наблюдение 1

Если число d делит и a, и b, то оно делит и a mod b.

Почему так:

• a = q * b + r, где r = a mod b;
• если d делит a и b, то оно делит и a - q * b, то есть r.

Значит, общие делители у пар (a, b) и (b, a mod b) одинаковые.

Наблюдение 2

Из-за этого наибольший общий делитель тоже не меняется:

• gcd(a, b) = gcd(b, a mod b).

Это и есть основа алгоритма Евклида.

Наблюдение 3

Если b = 0, то все числа, которые делят a, автоматически являются общими делителями пары (a, 0), потому что 0 делится на любое ненулевое число.

Поэтому:

• gcd(a, 0) = a.

В частности:

• gcd(0, 17) = 17;
• gcd(0, 0) = 0 по соглашению из условия.

Наблюдение 4

На каждом шаге второе число уменьшается:

• новый b равен a mod b,
• а остаток всегда меньше b.

Значит, процесс точно закончится.

3. Алгоритм

1. Считать a и b.
2. Пока b != 0:
   • вычислить остаток r = a % b;
   • присвоить a = b;
   • присвоить b = r.
3. Вывести a.

4. Почему это работает

Докажем, что алгоритм действительно находит НОД.

Пока b != 0, мы заменяем пару (a, b) на (b, a mod b).
По свойству алгоритма Евклида:

• gcd(a, b) = gcd(b, a mod b).

Значит, после каждого шага значение НОД не меняется.

Процесс продолжается до тех пор, пока b не станет равным 0.
В этот момент рассматривается пара (a, 0), а для неё:

• gcd(a, 0) = a.

Так как НОД не менялся на протяжении всех переходов, итоговое значение a и есть НОД исходных чисел.

Следовательно, алгоритм корректен.

5. Сложность

Алгоритм Евклида работает очень быстро.

• Время: O(log(min(a, b) + 1))
• Память: O(1)

Памяти почти не требуется, потому что используются только несколько переменных.

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;

    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    cout << a << '\n';
    return 0;
}

7. Код на Python 3

a, b = map(int, input().split())

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

print(a)