Когда оба числа равны нулю, результат не определён — подойдёт сколько угодно большое число. За исключением этого случая, верно следующее наблюдение: если одно из чисел равно нулю, то их $\gcd$ равен второму числу.
#Алгоритм нахождения
Алгоритм Евклида находит $\gcd$ двух чисел $a$ и $b$ за $O(\log \min(a, b))$, основываясь на следующей несложной формуле:
$$ \gcd(a, b) = \begin{cases} a, & b = 0 \\ \gcd(b,\, a - b), & b > 0 \end{cases} $$Здесь предполагается, что $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$:
$$ \gcd(a, b) = \begin{cases} a, & b = 0 \\ \gcd(b,\, a \bmod b), & b > 0 \end{cases} $$Реализация:
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)$ — это несложно доказать по индукции.