НОД и НОК

Наибольший общий делитель — самая частая арифметическая операция в олимпиадных задачах после сложения. Считается она за логарифм и в четыре строки.

Через разложение на множители

Сначала — откуда всё берётся. Любое число раскладывается на простые множители единственным образом:

$$24 = 2^3 \cdot 3, \qquad 60 = 2^2 \cdot 3 \cdot 5$$

НОД берёт каждое простое в наименьшей из двух степеней, НОК — в наибольшей:

$$\gcd(24, 60) = 2^2 \cdot 3 = 12, \qquad \mathrm{lcm}(24, 60) = 2^3 \cdot 3 \cdot 5 = 120$$

Отсюда сразу видно главное соотношение: для каждого простого сумма минимума и максимума равна сумме самих степеней, поэтому

$$\gcd(a, b) \cdot \mathrm{lcm}(a, b) = a \cdot b$$

Считать так на практике нельзя — раскладывать числа дорого. Но понимать через это стоит: почти все свойства НОД становятся очевидными.

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

Он опирается на одно наблюдение:

$$\gcd(a, b) = \gcd(b, a \bmod b)$$

long long gcd(long long a, long long b) {
    while (b) { long long rest = a % b; a = b; b = rest; }
    return a;
}

В C++ есть готовый std::gcd из <numeric>, в Python — math.gcd. Но написать самому стоит один раз, чтобы понимать, что происходит.

Почему это верно

Обозначим $d_1 = \gcd(a, b)$ и $d_2 = \gcd(b, a \bmod b)$. Покажем, что каждое делится на другое, — тогда они равны.

$d_1$ делит $a$ и $b$. Значит, делит и $a \bmod b = a - \lfloor a/b \rfloor \cdot b$ — разность кратных. Раз $d_1$ делит $b$ и $a \bmod b$, он делит и их наибольший общий делитель $d_2$.

Обратно: $d_2$ делит $b$ и $a \bmod b$, значит делит и $a = \lfloor a/b \rfloor \cdot b + (a \bmod b)$. Раз делит $a$ и $b$ — делит $d_1$.

Почему завершается

Остаток от деления на $b$ строго меньше $b$. Значит, второй аргумент строго убывает на каждом шаге, а убывать бесконечно неотрицательное целое не может. В какой-то момент он станет нулём, и мы придём к $\gcd(d, 0) = d$.

Скорость — логарифмическая: за два шага число уменьшается как минимум вдвое. Худший случай — соседние числа Фибоначчи; именно на них Евклид работает дольше всего.

НОК и переполнение

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;   // сначала делим!
}

Порядок действий важен. Запись a * b / gcd(a, b) даёт то же значение математически, но переполняется: произведение двух чисел до $10^9$ уже на грани, а до $10^{18}$ — заведомо за ней.

Деление первым безопасно, потому что $a$ гарантированно делится на $\gcd(a, b)$.

Отдельно стоит помнить, что сам НОК может переполниться. НОК десяти произвольных девятизначных чисел — число под девяносто знаков. Если в задаче НОК копится в цикле, нужна проверка на превышение предела и досрочный выход.

Что из этого следует

Общие делители $a$ и $b$ — это ровно делители $\gcd(a, b)$. Отсюда: чтобы посчитать, сколько чисел делят оба, считают НОД и перебирают его делители до корня — миллион шагов вместо триллиона.

Числа взаимно просты, если их НОД равен единице. Тогда их НОК равен произведению.

НОД нескольких чисел считается подряд: $\gcd(a, b, c) = \gcd(\gcd(a, b), c)$. Порядок не важен, и это позволяет считать НОД массива одним проходом.

НОД быстро вырождается. Каждое изменение делит предыдущее значение хотя бы на два, поэтому различных значений НОД по префиксам массива не больше логарифма. На этом стоят задачи вида «максимальный НОД по всем окнам длины $k$».