Алгоритм Евклида

Когда оба числа равны нулю, результат не определён — подойдёт сколько угодно большое число. За исключением этого случая, верно следующее наблюдение: если одно из чисел равно нулю, то их $\gcd$ равен второму числу.

#Алгоритм нахождения

Алгоритм Евклида находит $\gcd$ двух чисел $a$ и $b$ за $O(\log \min(a, b))$, основываясь на следующей несложной формуле:

Здесь предполагается, что $a > b$.

Докажем корректность этой формулы:

• Если $g = \gcd(a, b)$ делит и $a$, и $b$, то их разность $(a-b)$ тоже будет делиться на $g$.

• Никакой больший делитель $d$ числа $b$ не может делить число $(a-b)$: если $d > g$, то $d$ не может делить $a$, а значит и не делит $(a - b)$.

Прямая рекурсивная реализация:

int gcd(int a, int b) {
    if (a < b)
        swap(a, b);
    if (b == 0)
        return a;
    else
        return gcd(b, a - b);
}

Этот алгоритм может работать долго — например, на паре $(10^9, 1)$ он сделает миллиард итераций.

Идея дальнейшей оптимизации в том, чтобы вычитать из $a$ не одно $b$ за раз, а столько, чтобы в следующий раз $a$ и $b$ уже поменялись местами — чтобы новое $b$ стало меньше нового $a$. Простой способ этого достичь — просто вычесть $b$ из $a$ сразу максимально возможное число раз, то есть взять вместо нового $b$ остаток от деления $a$ на $b$:

Реализация:

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

Чуть более быстрая итеративная форма:

int gcd(int a, int b) {
    while (b > 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}

В современном C++ есть встроенная библиотечная функция gcd, которую рекомендуется использовать, не забывая про случай отрицательных чисел и $(0, 0)$.

Также помимо алгоритма Евклида существует в 2-3 раза более быстрый бинарный GCD.

#Время работы

Можно показать, что каждые две итерации меньшее число уменьшится хотя бы в два раза, а следовательно алгоритм работает за $O(\log \min (a, b))$. Эта оценка относится не только к худшему случаю, но и к среднему.

Примечательно, что худшие входные данные для алгоритма — это соседние числа Фибоначчи. На графике они видны как синие точки в пропорциях золотого сечения.

Также иногда полезно знать, что нахождение $\gcd$ группы из $n$ чисел от $1$ до $A$ будет работать не за $O(n \log A)$, а за $O(n + \log A)$ — это несложно доказать по индукции.