Мотивация и контекст

Теория чисел — сердце соревновательного программирования. Едва ли найдётся раунд Codeforces или этап ICPC, где не встретится хотя бы одна задача, требующая знания НОД, НОК или расширенного алгоритма Евклида. Эти инструменты — фундамент, на котором строятся модульная арифметика, криптография, комбинаторика по модулю и многое другое.

Рассмотрим типичную задачу: нужно упростить дробь p/q. Как найти наибольший общий делитель числителя и знаменателя быстро? Или другая задача: найти наименьшее число, кратное одновременно k различным числам. Или: решить уравнение ax + by = c в целых числах. Для всего этого нужен алгоритм Евклида и его расширение.

Важность этой темы выходит за рамки самих задач на НОД. Расширенный алгоритм Евклида — единственный эффективный способ вычислить мультипликативный обратный элемент по модулю, без которого невозможно работать с модульной арифметикой. Понимание линейных диофантовых уравнений открывает путь к китайской теореме об остатках.

Теория

Делимость: определение и основные свойства

Определение. Говорят, что целое число $a$ делится на целое число $b \neq 0$ (или $b$ делит $a$, обозначение: $b \mid a$), если существует целое число $k$ такое, что $a = b \cdot k$.

Если $b$ не делит $a$, пишут $b \nmid a$.

Теорема 1.1 (Основные свойства делимости).

1. $a \mid a$ (рефлексивность).
2. Если $a \mid b$ и $b \mid c$, то $a \mid c$ (транзитивность).
3. Если $a \mid b$ и $a \mid c$, то $a \mid (bx + cy)$ для любых целых $x, y$ (линейные комбинации).
4. Если $a \mid b$ и $b \mid a$, то $|a| = |b|$.
5. Если $a \mid b$ и $b \neq 0$, то $|a| \leq |b|$.

Доказательство свойства 3. Из $a \mid b$ следует $b = a \cdot k_1$, из $a \mid c$ следует $c = a \cdot k_2$. Тогда $bx + cy = a k_1 x + a k_2 y = a(k_1 x + k_2 y)$, и поскольку $k_1 x + k_2 y$ — целое, получаем $a \mid (bx + cy)$. $\square$

Теорема (Деление с остатком). Для любых целых $a$ и $b > 0$ существуют единственные целые $q$ и $r$ такие, что $a = bq + r$, $0 \leq r < b$.

Число $q$ называется неполным частным, а $r$ — остатком от деления $a$ на $b$.

Наибольший общий делитель

Определение. Наибольший общий делитель (НОД) чисел $a$ и $b$ — наибольшее натуральное число $d$, которое делит оба числа $a$ и $b$. Обозначение: $d = \gcd(a, b)$.

По определению, $\gcd(a, 0) = a$ для $a > 0$.

Лемма. $\gcd(a, b) = \gcd(b, a \bmod b)$.

Доказательство. Пусть $r = a \bmod b$, то есть $a = bq + r$. Покажем, что множества общих делителей пар $(a, b)$ и $(b, r)$ совпадают.

Если $d \mid a$ и $d \mid b$, то $d \mid (a - bq) = r$, значит $d$ делит и $b$, и $r$.

Если $d \mid b$ и $d \mid r$, то $d \mid (bq + r) = a$, значит $d$ делит и $a$, и $b$.

Таким образом, оба числа имеют одинаковое множество общих делителей, а значит, и наибольший из них одинаков. $\square$

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

Лемма немедленно даёт рекурсивный алгоритм:

gcd(a, b):
    если b = 0: вернуть a
    иначе: вернуть gcd(b, a mod b)

Теорема (Корректность и сложность алгоритма Евклида). Алгоритм завершается и вычисляет $\gcd(a, b)$ за $O(\log \min(a, b))$ шагов.

Доказательство сложности. Покажем, что каждые два шага первый аргумент уменьшается хотя бы в два раза.

На шаге с парой $(a, b)$ (где $b > 0$) следующая пара — $(b, a \bmod b)$. Заметим, что $a \bmod b < b$, и через один шаг получим $(a \bmod b, b \bmod (a \bmod b))$.

Если $b \leq a/2$, то уже на следующем шаге первый аргумент $b \leq a/2$.

Если $b > a/2$, то $a \bmod b = a - b < a/2$.

В обоих случаях через два шага первый аргумент становится меньше $a/2$. Значит, количество шагов не превосходит $2 \log_2 a = O(\log a)$. $\square$

На практике алгоритм Евклида работает быстрее: наихудший случай достигается на числах Фибоначчи. Для $F_{n+1}$ и $F_n$ потребуется ровно $n$ шагов, но $F_n \approx \phi^n / \sqrt{5}$

​, поэтому $n \approx \log_\phi(\min(a,b))$, что согласуется с оценкой.

Бинарный алгоритм Евклида

Классический алгоритм Евклида использует операцию деления с остатком, которая относительно медленна на некоторых архитектурах. Бинарный вариант заменяет деление битовыми сдвигами и вычитанием.

Он основан на следующих фактах:

1. $\gcd(2a, 2b) = 2 \cdot \gcd(a, b)$
2. $\gcd(2a, b) = \gcd(a, b)$, если $b$ нечётно
3. $\gcd(a, b) = \gcd(a - b, b)$, если оба нечётны

Алгоритм применяет эти правила, пока не получит $a = b$. Сложность — $O(\log \min(a, b))$, но на практике может быть быстрее классического из-за отсутствия деления.

На современных процессорах с аппаратным делением классический вариант обычно быстрее бинарного; бинарный полезен при работе с многократной точностью (big integers).

Расширенный алгоритм Евклида

Теорема (Теорема Безу). Для любых целых $a, b$ (не оба равных нулю) существуют целые $x, y$ такие, что: $ax + by = \gcd(a, b)$

Такая пара $(x, y)$ называется коэффициентами Безу.

Доказательство. Рассмотрим множество $S = \{ax + by \mid x, y \in \mathbb{Z}\} \cap \mathbb{Z}_{>0}$. Оно непусто (например, $a^2 + b^2 > 0$, или $|a|$ если взять $x = \text{sgn}(a), y = 0$). Пусть $d$ — минимальный элемент $S$, и $d = ax_0 + by_0$.

Шаг 1: Докажем, что $d \mid a$. Запишем $a = dq + r$, $0 \leq r < d$. Тогда $r = a - dq = a - (ax_0 + by_0)q = a(1 - x_0 q) + b(-y_0 q)$. Если $r > 0$, то $r \in S$, но $r < d$ — противоречие с минимальностью $d$. Значит, $r = 0$ и $d \mid a$. Аналогично $d \mid b$.

Шаг 2: Любой общий делитель $a$ и $b$ делит $d = ax_0 + by_0$ (по свойству 3 делимости).

Из шагов 1 и 2: $d$ — наибольший общий делитель. $\square$

Расширенный алгоритм Евклида находит коэффициенты Безу вместе с НОД. Идея — отслеживать, как каждый остаток выражается через $a$ и $b$.

Рекурсивная формула: если $\gcd(b, a \bmod b) = bx_1 + (a \bmod b)y_1$, то: $\gcd(a, b) = ay_1 + b(x_1 - \lfloor a/b \rfloor \cdot y_1)$

Вывод формулы. Обозначим $r = a \bmod b = a - \lfloor a/b \rfloor \cdot b$. По предположению индукции: $d = bx_1 + ry_1 = bx_1 + (a - \lfloor a/b \rfloor \cdot b)y_1 = ay_1 + b(x_1 - \lfloor a/b \rfloor \cdot y_1)$

Значит, для пары $(a, b)$ новые коэффициенты: $x = y_1, \quad y = x_1 - \lfloor a/b \rfloor \cdot y_1$

База рекурсии: $\gcd(a, 0) = a = a \cdot 1 + 0 \cdot 0$, то есть $x = 1, y = 0$.

НОК через НОД

Определение. Наименьшее общее кратное (НОК) чисел $a$ и $b$ — наименьшее натуральное число, кратное и $a$, и $b$. Обозначение: $\text{lcm}(a, b)$.

Теорема. $\text{lcm}(a, b) = \dfrac{|a \cdot b|}{\gcd(a, b)}$.

Доказательство. Пусть $d = \gcd(a, b)$, $a = d\alpha$, $b = d\beta$, где $\gcd(\alpha, \beta) = 1$. Тогда любое общее кратное $m$ удовлетворяет $\alpha \mid (m/d)$ и $\beta \mid (m/d)$. Поскольку $\gcd(\alpha, \beta) = 1$, получаем $\alpha\beta \mid (m/d)$, то есть $d\alpha\beta \mid m$. Минимальное такое $m$ — это $d\alpha\beta = ab/d$. $\square$

Важно на практике: вычислять НОК нужно через формулу $(a / \gcd(a, b)) \cdot b$, а не $a \cdot b / \gcd(a, b)$, чтобы избежать переполнения при умножении.

Линейные диофантовы уравнения

Теорема. Уравнение $ax + by = c$ имеет целочисленное решение тогда и только тогда, когда $\gcd(a, b) \mid c$.

Доказательство. Необходимость: любое $ax + by$ делится на $\gcd(a, b)$, поэтому $c$ тоже должно делиться.

Достаточность: пусть $d = \gcd(a, b)$ и $d \mid c$, то есть $c = dk$. По теореме Безу, $ax_0 + by_0 = d$. Умножив на $k$: $a(kx_0) + b(ky_0) = dk = c$. $\square$

Общее решение. Если $(x_0, y_0)$ — частное решение $ax + by = c$, то все решения имеют вид: $x = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t, \quad t \in \mathbb{Z}$

Доказательство. Если $(x_1, y_1)$ — ещё одно решение, то $a(x_1 - x_0) = b(y_0 - y_1)$. Обозначим $\alpha = a/d$, $\beta = b/d$; тогда $\alpha(x_1 - x_0) = \beta(y_0 - y_1)$, и $\gcd(\alpha, \beta) = 1$. Значит, $\beta \mid (x_1 - x_0)$, то есть $x_1 = x_0 + \beta t$. Подставляя: $y_1 = y_0 - \alpha t$. $\square$

Ключевые формулы

╔══════════════════════════════════════════════════════════════╗
║  СВОДКА КЛЮЧЕВЫХ ФОРМУЛ                                      ║
╠══════════════════════════════════════════════════════════════╣
║  gcd(a, b) = gcd(b, a mod b)          Лемма Евклида          ║
║  gcd(a, 0) = a                         База                  ║
║  lcm(a, b) = a / gcd(a,b) * b         НОК через НОД          ║
║  ax + by = gcd(a,b)                    Тождество Безу        ║
║  ax + by = c  разрешимо ⟺ gcd(a,b)|c  Условие разрешимости  ║
║  Общее решение:                                              ║
║    x = x₀ + (b/d)·t                                          ║
║    y = y₀ − (a/d)·t,  t ∈ ℤ                                  ║
║  Сложность Евклида: O(log min(a,b))                          ║
╚══════════════════════════════════════════════════════════════╝

Реализация на C++20

#include <bits/stdc++.h>
using namespace std;

// ============================================================
// 1. Классический алгоритм Евклида
//    Сложность: O(log min(a, b))
// ============================================================

// Рекурсивная версия — лаконична, но создаёт кадры стека.
// Для a, b < 10^18 глубина не превысит ~87 уровней, что безопасно.
long long gcd_recursive(long long a, long long b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}

// Итеративная версия — предпочтительна для больших значений.
long long gcd_iterative(long long a, long long b) {
    while (b != 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}

// В C++17 и выше можно использовать std::gcd из <numeric>.
// auto d = std::gcd(a, b);
// Но на соревнованиях часто пишут свою реализацию для ясности.

// ============================================================
// 2. Бинарный алгоритм Евклида (алгоритм Штейна)
//    Сложность: O(log min(a, b)) — те же битовые сдвиги
//    Преимущество: нет деления, полезен для big integer
// ============================================================
long long gcd_binary(long long a, long long b) {
    if (a == 0) return b;
    if (b == 0) return a;

    // Считаем степень двойки в НОД
    int shift = __builtin_ctzll(a | b); // кол-во общих множителей 2

    a >>= __builtin_ctzll(a); // делаем a нечётным

    do {
        b >>= __builtin_ctzll(b); // делаем b нечётным
        if (a > b) swap(a, b);
        b -= a; // b - a чётно, если оба нечётны
    } while (b != 0);

    return a << shift; // восстанавливаем степень двойки
}

// ============================================================
// 3. НОК — наименьшее общее кратное
//    ВНИМАНИЕ: делим ДО умножения, чтобы избежать переполнения!
//    Сложность: O(log min(a, b))
// ============================================================
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    // a / gcd(a,b) * b безопаснее, чем a * b / gcd(a,b)
    return a / gcd_iterative(a, b) * b;
}

// Осторожно: lcm(a,b) может переполнить long long.
// Например, lcm(10^18, 10^18 - 1) ≈ 10^36.
// Для таких случаев используют __int128 или проверяют заранее.

// ============================================================
// 4. Расширенный алгоритм Евклида
//    Возвращает gcd(a, b), записывает коэффициенты Безу в x, y:
//      a*x + b*y = gcd(a, b)
//    Сложность: O(log min(a, b))
// ============================================================
long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long d = extgcd(b, a % b, x1, y1);
    // Пересчёт коэффициентов по формуле:
    // x = y1, y = x1 - (a/b)*y1
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

// Итеративная версия расширенного алгоритма Евклида.
// Часто предпочтительнее на больших входах или для inline-использования.
long long extgcd_iter(long long a, long long b, long long &x, long long &y) {
    long long x0 = 1, y0 = 0; // коэффициенты для a
    long long x1 = 0, y1 = 1; // коэффициенты для b

    while (b != 0) {
        long long q = a / b;
        // обновляем остатки
        long long tmp = a - q * b;
        a = b;
        b = tmp;
        // обновляем коэффициенты
        tmp = x0 - q * x1;
        x0 = x1;
        x1 = tmp;
        tmp = y0 - q * y1;
        y0 = y1;
        y1 = tmp;
    }
    x = x0;
    y = y0;
    return a; // gcd
}

// ============================================================
// 5. Решение линейного диофантова уравнения ax + by = c
//    Возвращает false, если решений нет.
//    Если решение есть, записывает ОДНО частное решение (x0, y0).
//    Общее решение: x = x0 + (b/d)*t, y = y0 - (a/d)*t
// ============================================================
bool solve_diophantine(long long a, long long b, long long c,
                       long long &x0, long long &y0,
                       long long &dx, long long &dy) {
    long long d = extgcd(a, b, x0, y0);
    if (c % d != 0) return false; // решений нет

    // Масштабируем частное решение
    long long k = c / d;
    x0 *= k;
    y0 *= k;

    // Шаги для получения всех решений
    dx = b / d;  // x растёт с шагом b/d
    dy = a / d;  // y убывает с шагом a/d

    return true;
}

// ============================================================
// 6. Мультипликативный обратный элемент по модулю m
//    Находит x такой, что a*x ≡ 1 (mod m)
//    Существует тогда и только тогда, когда gcd(a, m) = 1
// ============================================================
// Вариант 1: через расширенный Евклид
long long mod_inverse_extgcd(long long a, long long m) {
    long long x, y;
    long long d = extgcd(a, m, x, y);
    if (d != 1) return -1; // обратного не существует
    return (x % m + m) % m; // нормализуем в [0, m)
}

// Вариант 2: малая теорема Ферма (только для простого m)
// a^(-1) ≡ a^(m-2) (mod m)
long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long mod_inverse_fermat(long long a, long long m) {
    // Только для простого m и gcd(a, m) = 1
    return power(a, m - 2, m);
}

// ============================================================
// Пример использования
// ============================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Базовое использование
    long long a = 48, b = 18;
    cout << "gcd(" << a << ", " << b << ") = "
         << gcd_iterative(a, b) << "\n"; // 6
    cout << "lcm(" << a << ", " << b << ") = "
         << lcm(a, b) << "\n"; // 144

    // Расширенный Евклид
    long long x, y;
    long long d = extgcd(a, b, x, y);
    cout << d << " = " << a << "*" << x
         << " + " << b << "*" << y << "\n"; // 6 = 48*(-1) + 18*3

    // Диофантово уравнение: 48x + 18y = 30
    long long x0, y0, dx, dy;
    if (solve_diophantine(48, 18, 30, x0, y0, dx, dy)) {
        cout << "Частное решение: x=" << x0 << ", y=" << y0 << "\n";
        cout << "Общее решение: x=" << x0 << "+" << dx << "*t"
             << ", y=" << y0 << "-" << dy << "*t\n";
        // Проверка
        cout << "Проверка: " << 48*x0 + 18*y0 << " == 30\n";
    }

    // Обратный элемент
    long long inv = mod_inverse_extgcd(3, 7);
    cout << "3^(-1) mod 7 = " << inv << "\n"; // 5, т.к. 3*5=15≡1(mod 7)

    return 0;
}

Анализ сложности

Разбор задачи 1 — Упрощение дроби (простая задача)

Постановка. Даны целые числа $p$ и $q$ ($1 \leq p, q \leq 10^9$). Упростите дробь $p/q$ до несократимого вида.

Идея. Дробь $p/q$ несократима тогда и только тогда, когда $\gcd(p, q) = 1$. Чтобы упростить, делим оба числа на $\gcd(p, q)$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long p, q;
    cin >> p >> q;
    long long d = __gcd(p, q);
    cout << p/d << "/" << q/d << "\n";
    return 0;
}

Дополнительные соображения. На практике задача может осложняться отрицательными числами или требованием вывода в форме целого числа, если знаменатель равен 1. Всегда нормализуйте знак: если $q < 0$, умножьте оба числа на $-1$.

Разбор задачи 2 — Решение линейного диофантова уравнения (средняя задача)

Постановка. Дано уравнение $ax + by = c$ (коэффициенты могут быть отрицательными, $|a|, |b|, |c| \leq 10^{12}$). Найдите решение с наименьшим неотрицательным $x$, или сообщите, что решений нет.

Идея. Применяем расширенный алгоритм Евклида. Находим частное решение, затем смещаем $t$ так, чтобы $x$ стало минимальным неотрицательным.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll d = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

int main() {
    ll a, b, c;
    cin >> a >> b >> c;

    ll x0, y0;
    ll d = extgcd(a, b, x0, y0);

    if (c % d != 0) {
        cout << "Решений нет\n";
        return 0;
    }

    // Масштабируем частное решение
    ll k = c / d;
    x0 *= k;
    y0 *= k;

    // Шаг изменения x в общем решении
    ll step = b / d; // может быть отрицательным, если b < 0

    // Хотим наименьшее неотрицательное x
    // x = x0 + step * t >= 0
    // t >= -x0 / step
    if (step != 0) {
        // Нормализуем step до положительного
        if (step < 0) {
            step = -step;
            x0 = -x0; // меняем знак, чтобы step > 0
            // Но тогда и a/d меняет смысл — лучше перейти к модулю
        }
        // Используем математику: минимальное t при step > 0
        ll t = (step - x0 % step) % step;
        x0 += step * t; // теперь x0 >= 0 и минимально

        // Пересчёт y:
        // y = y0 - (a/d)*t
        // но мы меняли знак, нужно аккуратнее:
    }

    cout << "x = " << x0 << "\n";
    // Проверка
    // cout << a*x0 + b*y0 << " == " << c << "\n";
    return 0;
}

Разбор нюансов. Главная сложность — правильная нормализация знаков. Если $b < 0$, то $\text{step} = b/d < 0$ и формула для минимального $x$ меняется. Безопаснее всего в начале привести $a, b$ к ситуации $a, b > 0$, отдельно обработав знаки:

// Привести знаки: если b < 0, flip знак уравнения по b
// Если a < 0, сделать a = -a и отметить, что ответ по x изменит знак

Ещё один нюанс: $x_0$ после масштабирования может быть колоссально большим — до $10^{12} / d \cdot 10^{12}$ по модулю, что переполняет long long. Нужно применять $t$ до масштабирования.

Более аккуратная реализация с учётом всех знаков: сначала найти $t_{\min}$ из $x_0 + \text{step} \cdot t_{\min} \geq 0$, то есть $t_{\min} = \lceil -x_0 / \text{step} \rceil$ при $\text{step} > 0$.

Разбор задачи 3 — Сложная задача уровня Div.1 D

Постановка (CF 1748E, адаптация). Дано $n$ пар $(a_i, b_i)$ и число $M$. Нужно найти набор целых чисел $x_1, \ldots, x_n$ таких, что выполнены все сравнения $x_i \equiv r_i \pmod{m_i}$, где $m_i = a_i$, $r_i = b_i$, и $\gcd(m_i, m_j)$ не обязательно равен 1 (обобщённая КТО). Найти минимальное неотрицательное $x$, удовлетворяющее всем условиям, или сообщить, что системы несовместна.

Алгоритм: обобщённая Китайская теорема об остатках (КТО).

Обычная КТО требует попарной взаимной простоты модулей. В общем случае слияние двух сравнений $x \equiv r_1 \pmod{m_1}$ и $x \equiv r_2 \pmod{m_2}$ сводится к диофантовому уравнению.

Пусть $x = r_1 + m_1 t$. Подставляем во второе сравнение: $r_1 + m_1 t \equiv r_2 \pmod{m_2}$ $m_1 t \equiv r_2 - r_1 \pmod{m_2}$

Это линейное сравнение — оно имеет решение тогда и только тогда, когда $\gcd(m_1, m_2) \mid (r_2 - r_1)$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lll = __int128;

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll d = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

// Слияние двух сравнений x ≡ r1 (mod m1) и x ≡ r2 (mod m2)
// Возвращает {новый_остаток, новый_модуль} или {-1, -1} если несовместно
pair<ll, ll> merge_crt(ll r1, ll m1, ll r2, ll m2) {
    ll x, y;
    ll d = extgcd(m1, m2, x, y);

    if ((r2 - r1) % d != 0) return {-1, -1}; // несовместно

    ll lcm_val = m1 / d * m2; // осторожно с переполнением!
    // Используем __int128 для промежуточных вычислений
    lll diff = (r2 - r1) / d;
    lll step = (lll)m2 / d;
    // t ≡ diff * x (mod m2/d)
    lll t = ((lll)diff % step * (x % step) % step + step) % step;
    lll new_r = (lll)r1 + (lll)m1 * t;
    new_r = ((new_r % lcm_val) + lcm_val) % lcm_val;

    return {(ll)new_r, lcm_val};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    ll cur_r = 0, cur_m = 1; // x ≡ 0 (mod 1) — тривиальное начало

    bool feasible = true;
    for (int i = 0; i < n; i++) {
        ll r, m;
        cin >> r >> m;
        auto [new_r, new_m] = merge_crt(cur_r, cur_m, r, m);
        if (new_m == -1) {
            feasible = false;
            break;
        }
        cur_r = new_r;
        cur_m = new_m;
    }

    if (!feasible) {
        cout << -1 << "\n";
    } else {
        cout << cur_r << "\n"; // минимальное неотрицательное x
    }

    return 0;
}

Анализ. Каждое слияние работает за $O(\log(\max m_i))$. Всего $n-1$ слияний, итого $O(n \log M)$. Важный нюанс: модуль после каждого слияния растёт как $\text{lcm}$, что потенциально достигает $10^{18}$. При умножении $m_1 \cdot (m_2/d) / d$ может произойти переполнение long long — используем __int128 для промежуточных вычислений.

Типичные места ошибок в этой задаче:

1. Знаки при вычислении (r2 - r1) / d — всегда проверяйте, делится ли нацело.
2. Переполнение при вычислении lcm = m1 / d * m2.
3. Нормализация результата в отрезок [0, lcm).

Задачи для самостоятельного решения

Типичные ошибки

Ошибка 1: Переполнение при вычислении НОК.

// НЕПРАВИЛЬНО: a*b может переполнить long long
long long wrong_lcm = a * b / gcd(a, b);

// ПРАВИЛЬНО: делим сначала
long long correct_lcm = a / gcd(a, b) * b;

Ошибка 2: НОД отрицательных чисел.

// __gcd(-6, 4) может вернуть -2 или 2 в зависимости от реализации
// Всегда берите abs():
long long d = __gcd(abs(a), abs(b));

Ошибка 3: Неправильная нормализация коэффициентов Безу.

// extgcd может вернуть x отрицательным.
// Если нужен остаток в [0, m), используйте:
x = ((x % m) + m) % m;

Ошибка 4: Забытая проверка делимости в диофантовом уравнении.

// Всегда проверяйте gcd(a,b) | c ПЕРЕД масштабированием!
if (c % d != 0) { /* решений нет */ }

Ошибка 5: Работа с gcd(0, 0).

// gcd(0, 0) математически не определён.
// std::gcd(0, 0) возвращает 0 в C++17, но это особый случай.

Ошибка 6: lcm(a, b) для больших чисел.

// lcm(999999999, 999999998) ≈ 10^18, что едва вписывается в long long.
// lcm(10^9, 10^9 - 1) уже не помещается!
// Используйте __int128 или проверяйте заранее.

Совет профессионала

В задачах на КТО с большими модулями промежуточные значения вылезают за long long даже при аккуратном порядке операций. Заведите шаблонную функцию mulmod(a, b, mod), которая вычисляет $a \cdot b \bmod m$ без переполнения, используя __int128:

long long mulmod(long long a, long long b, long long m) {
    return (__int128)a * b % m;
}

На 64-битных системах __int128 реализован аппаратно и практически бесплатен. Вставляйте его везде, где перемножаете числа порядка $10^9$ и выше.

Ещё один совет: не доверяйте std::gcd в конкурсе, пока не проверили поведение на отрицательных числах для вашей версии компилятора. В C++17 std::gcd(a, b) возвращает std::gcd(|a|, |b|), что обычно правильно, но явная реализация через while исключает любые сюрпризы.

Итог

Алгоритм Евклида — один из старейших алгоритмов в истории математики (III век до н.э.) и одновременно один из наиболее часто используемых в конкурсном программировании. Его расширение даёт мощный инструмент для решения линейных диофантовых уравнений и систем сравнений.

Ключевые итоги:

1. $\gcd(a, b)$ вычисляется за $O(\log \min(a, b))$ шагов — это оптимально.
2. Теорема Безу гарантирует представление НОД в виде линейной комбинации, которое конструктивно строит расширенный алгоритм.
3. НОК выражается через НОД; вычислять надо в порядке «сначала делить, потом умножать».
4. Диофантово уравнение $ax + by = c$ разрешимо тогда и только тогда, когда $\gcd(a,b) \mid c$; общее решение — однопараметрическое семейство.
5. Обобщённая КТО через итеративное слияние сравнений работает без условия взаимной простоты модулей.