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

Представьте задачу: вы знаете, что некоторое число N при делении на 3 даёт остаток 2, при делении на 5 — остаток 3, при делении на 7 — остаток 2. Каково наименьшее N? Ответ — 23. Именно такие системы уравнений решает Китайская теорема об остатках.

Название «Китайская» связано с трактатом «Математика в девяти главах» (около III века н.э.), где описана задача о подсчёте солдат: нужно найти число, при делении которого на 3 остаток 2, на 5 — 3, на 7 — 2. Это одна из старейших задач в истории математики.

В современном программировании КТО встречается везде:

• NTT с несколькими модулями: произведение многочленов считается по трём разным модулям (например, 998244353, 985661441, 754974721), а затем ответ восстанавливается по КТО.
• Хранение больших чисел: число с тысячами цифр можно хранить как набор остатков и восстановить тогда, когда нужно.
• Конкурентная криптография: RSA-CRT ускоряет дешифрование в два раза.
• Подсчёт перестановок с ограничениями: сводится к системам сравнений.

Теория

Формулировка КТО

Теорема (Китайская теорема об остатках). Пусть m₁, m₂, …, mₖ — попарно взаимно простые натуральные числа (то есть gcd(mᵢ, mⱼ) = 1 при i ≠ j). Тогда система сравнений

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)

имеет единственное решение по модулю M = m₁ · m₂ · … · mₖ.

Доказательство.

Обозначим Mᵢ = M / mᵢ (произведение всех модулей кроме mᵢ). Так как gcd(Mᵢ, mᵢ) = 1 (все множители попарно взаимно просты), существует yᵢ — обратный к Mᵢ по модулю mᵢ, то есть Mᵢ · yᵢ ≡ 1 (mod mᵢ).

Построим решение:

x = a₁ · M₁ · y₁ + a₂ · M₂ · y₂ + … + aₖ · Mₖ · yₖ  (mod M)

Проверка. Рассмотрим x mod mᵢ. Для всех j ≠ i: Mⱼ = M / mⱼ кратно mᵢ (так как mᵢ входит в произведение M, но не исключён при j ≠ i). Значит aⱼ · Mⱼ · yⱼ ≡ 0 (mod mᵢ) при j ≠ i. Остаётся только член aᵢ · Mᵢ · yᵢ ≡ aᵢ · 1 ≡ aᵢ (mod mᵢ).

Единственность. Пусть x и x' — два решения. Тогда mᵢ | (x − x') для всех i. Так как mᵢ попарно взаимно просты, M = ∏mᵢ делит x − x'. Значит, x ≡ x' (mod M).

Изоморфизм колец

Более элегантная формулировка: при взаимно простых mᵢ отображение

φ: Z_M → Z_{m₁} × Z_{m₂} × … × Z_{mₖ} x ↦ (x mod m₁, x mod m₂, …, x mod mₖ)

является изоморфизмом колец. КТО утверждает, что φ — биекция, а алгебраические свойства сохраняются: сложение и умножение компонент соответствуют операциям в Z_M.

Следствие: если нужно вычислить f(x) mod M (где M = m₁·…·mₖ), достаточно вычислить f(x) mod mᵢ для каждого i и восстановить ответ. Это разрывает зависимость между модулями и позволяет делать вычисления по маленьким модулям параллельно.

Алгоритм Гарнера — восстановление в смешанной системе счисления

Прямое вычисление x = ∑ aᵢ · Mᵢ · yᵢ требует работы с числами порядка M, что при большом числе модулей неудобно. Алгоритм Гарнера представляет решение в виде смешанного основания:

x = c₀ + c₁·m₁ + c₂·m₁·m₂ + c₃·m₁·m₂·m₃ + …

где 0 ≤ cᵢ < mᵢ₊₁. Это позволяет работать с большими числами через длинную арифметику, избегая работы в кольце Z_M.

Нахождение коэффициентов cᵢ:

c₀ = a₀ (mod m₁) — просто

c₁ = (a₁ − c₀) · m₁⁻¹ (mod m₂)

c₂ = ((a₂ − c₀) · m₁⁻¹ − c₁) · m₂⁻¹ (mod m₃)

и т.д. Коэффициент cᵢ вычисляется по модулю mᵢ₊₁, поэтому числа маленькие.

Доказательство (для двух модулей): При i = 1: x ≡ c₀ + c₁·m₁ (mod m₁·m₂). Из x ≡ a₀ (mod m₁): c₀ ≡ a₀ (mod m₁) → c₀ = a₀ mod m₁. Из x ≡ a₁ (mod m₂): c₀ + c₁·m₁ ≡ a₁ (mod m₂) → c₁ ≡ (a₁ − c₀) · m₁⁻¹ (mod m₂).

Обобщённая КТО (модули не взаимно просты)

Что делать, если gcd(mᵢ, mⱼ) > 1? Система:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)

разрешима тогда и только тогда, когда a₁ ≡ a₂ (mod gcd(m₁, m₂)).

Доказательство. x ≡ a₁ (mod m₁) означает x = a₁ + k₁·m₁. Подставляя во второе уравнение: a₁ + k₁·m₁ ≡ a₂ (mod m₂), то есть k₁·m₁ ≡ a₂ − a₁ (mod m₂). Это линейное сравнение разрешимо тогда и только тогда, когда gcd(m₁, m₂) делит a₂ − a₁. Если разрешимо, решение единственно по модулю lcm(m₁, m₂) = m₁·m₂ / gcd(m₁, m₂).

Конструкция решения: находим k₁ через расширенный Евклид, получаем x = a₁ + k₁·m₁, новый модуль lcm(m₁, m₂).

Итеративное объединение — алгоритм для k модулей

Система из k уравнений решается итеративно: объединяем первые два, получаем одно уравнение по модулю lcm(m₁, m₂), затем объединяем его с третьим и т.д.

для i от 2 до k:
    объединить текущее решение (x, M) с (aᵢ, mᵢ)
    → новое (x, lcm(M, mᵢ)) или сообщить «нет решения»

Каждый шаг — O(log mᵢ) для gcd и расш. Евклида. Итого — O(k · log M).

Ключевые формулы (сводка)

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

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

// ─────────────────────────────────────────────────────────────────
// Утилиты: gcd, extended_gcd, power
// ─────────────────────────────────────────────────────────────────
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Безопасное умножение через __int128, чтобы избежать переполнения
// при mod до ~4.6 * 10^18
ll mulmod(ll a, ll b, ll mod) {
    return (lll)a * b % mod;
}

// ─────────────────────────────────────────────────────────────────
// Объединение двух сравнений (итеративный шаг обобщённой КТО)
// x ≡ r1 (mod m1),  x ≡ r2 (mod m2)
// Возвращает {r, m} — решение по модулю lcm(m1, m2), или {-1, -1} если несовместна
// Сложность: O(log min(m1, m2))
// ─────────────────────────────────────────────────────────────────
pair<ll,ll> combine_crt(ll r1, ll m1, ll r2, ll m2) {
    // Ищем x = r1 + k * m1, k такое, что r1 + k*m1 ≡ r2 (mod m2)
    // k * m1 ≡ (r2 - r1) (mod m2)
    // gcd(m1, m2) должен делить (r2 - r1)
    ll x, y;
    ll g = extended_gcd(m1, m2, x, y);
    ll diff = ((r2 - r1) % m2 + m2) % m2;
    if (diff % g != 0) return {-1, -1};  // несовместна

    ll lcm = m1 / g * m2;  // делим до умножения, чтобы избежать переполнения
    // k = x * (diff / g) mod (m2 / g)
    ll step = m2 / g;
    ll k = mulmod(x % step, (diff / g) % step, step);
    k = (k % step + step) % step;
    ll r = r1 + k * m1;
    r = ((r % lcm) + lcm) % lcm;
    return {r, lcm};
}

// ─────────────────────────────────────────────────────────────────
// Решение системы сравнений — итеративный метод
// Принимает вектор {(остаток, модуль)}
// Возвращает {решение, lcm модулей} или {-1, -1} если системы несовместна
// Сложность: O(k * log M)
// ─────────────────────────────────────────────────────────────────
pair<ll,ll> solve_crt(vector<pair<ll,ll>> congruences) {
    ll r = 0, m = 1;
    for (auto [ri, mi] : congruences) {
        auto [new_r, new_m] = combine_crt(r, m, ri, mi);
        if (new_r == -1) return {-1, -1};
        r = new_r;
        m = new_m;
    }
    return {r, m};
}

// ─────────────────────────────────────────────────────────────────
// Прямая КТО (взаимно простые модули)
// Стандартная формула: x = sum(ai * Mi * yi) mod M
// Сложность: O(k * log M)
// ─────────────────────────────────────────────────────────────────
ll crt_direct(vector<ll> a, vector<ll> m) {
    int k = a.size();
    ll M = 1;
    for (ll mi : m) M *= mi;

    ll x = 0;
    for (int i = 0; i < k; ++i) {
        ll Mi = M / m[i];
        ll xi, yi;
        extended_gcd(Mi % m[i], m[i], xi, yi);
        ll yi_mod = (xi % m[i] + m[i]) % m[i];
        // x += a[i] * Mi * yi_mod, но осторожно с переполнением
        // используем __int128
        x = (x + (lll)a[i] % M * (Mi % M) % M * (yi_mod % M)) % M;
    }
    return x;
}

// ─────────────────────────────────────────────────────────────────
// Алгоритм Гарнера
// Позволяет восстановить большое число x через смешанное основание
// Используется, когда M слишком большое для ll (например, при NTT)
// Возвращает коэффициенты в смешанном основании, умноженные на произведения модулей
// ─────────────────────────────────────────────────────────────────
// Для случая восстановления числа по трём NTT-модулям:
struct Garner {
    // Модули должны быть попарно взаимно простыми
    // Заранее вычислим обратные: inv[i][j] = m[i]^{-1} mod m[j], i < j
    static const int MAXK = 10;
    ll inv[MAXK][MAXK];
    vector<ll> mods;

    Garner(vector<ll> m) : mods(m) {
        int k = m.size();
        for (int i = 0; i < k; ++i)
            for (int j = i+1; j < k; ++j) {
                ll xi, yi;
                extended_gcd(m[i] % m[j], m[j], xi, yi);
                inv[i][j] = (xi % m[j] + m[j]) % m[j];
            }
    }

    // Восстанавливает x mod output_mod из остатков r[0..k-1]
    // Сложность: O(k^2)
    ll restore(vector<ll> r, ll output_mod) {
        int k = mods.size();
        // Вычисляем коэффициенты c[i] алгоритма Гарнера
        vector<ll> c = r;  // c[i] будет подправляться
        for (int i = 1; i < k; ++i) {
            // c[i] = (r[i] - c[0] - c[1]*m[0] - ... - c[i-1]*m[0]*...*m[i-2]) * продукт^{-1} mod m[i]
            ll val = c[i];
            ll coeff = 1;
            for (int j = 0; j < i; ++j) {
                val = (val - c[j] % mods[i] * coeff % mods[i] + mods[i] * 2) % mods[i];
                coeff = coeff * mods[j] % mods[i];
            }
            c[i] = val % mods[i] * inv[/* see below */0][i] % mods[i];
            // Упрощённая версия — вычисляем inv произведения явно
            ll prod_inv = 1;
            for (int j = 0; j < i; ++j) {
                ll xi, yi;
                extended_gcd(mods[j] % mods[i], mods[i], xi, yi);
                prod_inv = prod_inv * ((xi % mods[i] + mods[i]) % mods[i]) % mods[i];
            }
            c[i] = val % mods[i] * prod_inv % mods[i];
        }
        // Восстанавливаем x mod output_mod
        ll result = 0, prefix = 1;
        for (int i = 0; i < k; ++i) {
            result = (result + c[i] % output_mod * (prefix % output_mod)) % output_mod;
            prefix = prefix * (mods[i] % output_mod) % output_mod;
        }
        return result;
    }
};

// ─────────────────────────────────────────────────────────────────
// Функция для восстановления числа из трёх NTT-остатков
// Используется в многомодульном NTT
// MOD1, MOD2, MOD3 — три NTT-дружественных простых числа
// ─────────────────────────────────────────────────────────────────
const ll MOD1 = 998244353;   // 119 * 2^23 + 1
const ll MOD2 = 985661441;   // 235 * 2^22 + 1
const ll MOD3 = 754974721;   // 45  * 2^24 + 1

// Восстанавливает коэффициент многочлена из трёх остатков
// output_mod — финальный модуль задачи
ll garner_3(ll r1, ll r2, ll r3, ll output_mod) {
    auto solve_inv = [](ll a, ll m) -> ll {
        ll x, y; extended_gcd(a % m, m, x, y); return (x % m + m) % m;
    };
    // x ≡ r1 (mod MOD1)
    // x = r1 + c1 * MOD1
    // c1 = (r2 - r1) / MOD1 mod MOD2
    ll c1 = (r2 - r1 % MOD2 + MOD2) % MOD2 * solve_inv(MOD1, MOD2) % MOD2;
    // x = r1 + c1*MOD1 + c2*MOD1*MOD2
    // c2 mod MOD3:
    ll tmp = (r1 + c1 % MOD3 * (MOD1 % MOD3)) % MOD3;
    ll c2 = (r3 - tmp + MOD3) % MOD3 * solve_inv(MOD1 % MOD3 * MOD2 % MOD3, MOD3) % MOD3;
    // Результат mod output_mod:
    ll result = r1 % output_mod;
    result = (result + c1 % output_mod * (MOD1 % output_mod)) % output_mod;
    result = (result + c2 % output_mod * (MOD1 % output_mod) % output_mod * (MOD2 % output_mod)) % output_mod;
    return result;
}

// ─────────────────────────────────────────────────────────────────
// Демонстрация
// ─────────────────────────────────────────────────────────────────
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Пример 1: классическая КТО
    // x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) → x = 23 (mod 105)
    auto [r, m] = solve_crt({{2, 3}, {3, 5}, {2, 7}});
    cout << "x = " << r << " (mod " << m << ")\n";  // 23 (mod 105)

    // Пример 2: несовместная система
    auto [r2, m2] = solve_crt({{1, 4}, {2, 6}});
    // x ≡ 1 (mod 4), x ≡ 2 (mod 6) — несовместна (gcd(4,6)=2, но 1 ≢ 2 mod 2)
    if (r2 == -1) cout << "Несовместна\n";

    // Пример 3: совместная с НЕ взаимно простыми
    // x ≡ 3 (mod 4), x ≡ 7 (mod 6) → gcd=2, 3≡1 mod 2, 7≡1 mod 2 — совместна
    auto [r3, m3] = solve_crt({{3, 4}, {7, 6}});
    cout << "x = " << r3 << " (mod " << m3 << ")\n";  // 7 (mod 12)

    return 0;
}

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

Разбор задачи 1 — Восстановление числа из остатков

Условие. Дано k пар (aᵢ, mᵢ), 1 ≤ k ≤ 10^5. Модули взаимно простые, каждый mᵢ ≤ 10^9. Найти наименьшее неотрицательное x, удовлетворяющее всем сравнениям, или сообщить что решения нет. (Codeforces 687E-style)

Разбор. Прямое применение итеративной КТО. Объединяем пары по одной: каждый шаг расширяет текущий модуль. Единственная сложность — переполнение: lcm(m₁, …, mₖ) может быть больше long long.

Ключевые наблюдения:

1. Если модули простые и меньше 10^9, их произведение может достигать (10^9)^(10^5) — это не помещается ни в какой тип. Значит, либо k мало (≤ 18, чтобы 2^60 ≈ 10^18), либо нужна длинная арифметика.
2. На практике в задачах модули обычно заданы так, что lcm умещается в long long.
3. Функция combine_crt из кода выше обрабатывает переполнение через деление m1/g до умножения.

int main() {
    int k; cin >> k;
    vector<pair<ll,ll>> congruences(k);
    for (auto &[a, m] : congruences) cin >> a >> m;

    auto [r, M] = solve_crt(congruences);
    if (r == -1) { cout << -1 << "\n"; return 0; }
    cout << (r % M + M) % M << "\n";
    return 0;
}

Проверка: для примера {(2,3), (3,5), (2,7)}:

• Шаг 1: объединяем (2,3) и (3,5). k=m₁·m₂/gcd=15, diff=1, inv(3 mod 5)=2, k_val=(1·2)%5=2, x=2+2·3=8 (mod 15).
• Шаг 2: объединяем (8,15) и (2,7). diff=(2−8+21)%7=0, k=0, x=8 (mod 105).
• Проверка: 8 mod 7 = 1 ≠ 2... Пересчитаем: diff = (2−8 mod 7+7)%7 = (2−1+7)%7 = 1. inv(15 mod 7) = inv(1) = 1. k=1, x=8+1·15=23. ✓

Разбор задачи 2 — Подсчёт перестановок с ограничениями (средняя)

Условие. Найти количество целых чисел от 1 до N, которые при делении на каждое из простых pᵢ ∈ {p₁, …, pₖ} дают остатки rᵢ. N ≤ 10^18, k ≤ 15, pᵢ < 100.

Разбор. Это задача о подсчёте чисел в арифметической прогрессии с шагом M = p₁·p₂·…·pₖ.

Пусть x₀ — решение системы по КТО по модулю M. Нам нужно посчитать, сколько чисел вида x₀ + t·M лежит в [1, N].

t = 0, 1, 2, ..., floor((N - x₀) / M)

Если x₀ > N — ответ 0. Иначе ответ = ⌊(N − x₀) / M⌋ + 1.

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

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

pair<ll,ll> combine_crt(ll r1, ll m1, ll r2, ll m2) {
    ll x, y; ll g = extended_gcd(m1, m2, x, y);
    ll diff = ((r2-r1)%m2+m2)%m2;
    if (diff%g) return {-1,-1};
    ll step = m2/g;
    ll lcm_val = m1/g*m2;
    ll k = (lll)x%step * ((diff/g)%step) % step;
    k = (k%step+step)%step;
    ll r = r1 + (lll)k*m1 % lcm_val;
    return {r%lcm_val, lcm_val};
}

int main() {
    ll N; int k; cin >> N >> k;
    vector<pair<ll,ll>> congruences(k);
    for (auto &[r, m] : congruences) cin >> r >> m;

    auto [x0, M] = [&]() -> pair<ll,ll> {
        ll r=0, m=1;
        for (auto [ri, mi] : congruences) {
            auto [nr, nm] = combine_crt(r, m, ri, mi);
            if (nr == -1) return {-1,-1};
            r=nr; m=nm;
        }
        return {r, m};
    }();

    if (x0 == -1 || x0 == 0) {
        // x0=0 означает, что минимальное решение — M само по себе
        // (r=0 mod M, но мы ищем в [1, N])
        if (x0 == 0) x0 = M;
    }
    if (x0 == -1 || x0 > N) { cout << 0 << "\n"; return 0; }
    cout << (N - x0) / M + 1 << "\n";
    return 0;
}

Пример: N = 100, система: x ≡ 2 (mod 3), x ≡ 1 (mod 5). Решение x₀ = 11 (mod 15). Чисел: (100 − 11)/15 + 1 = 6 + 1 = 7. Проверка: 11, 26, 41, 56, 71, 86, 101 — 101 > 100, значит 6? Пересчитаем: (100−11)/15 = 89/15 = 5, +1 = 6. ✓

Разбор задачи 3 — Многомодульный NTT и восстановление коэффициентов (Codeforces Div.1 D / ICPC WF уровень)

Условие. Перемножить два многочлена с коэффициентами до 10^9 и n ≤ 10^6 членов. Вывести коэффициенты результирующего многочлена по модулю P = 10^9 + 7.

Проблема. Стандартный NTT работает по фиксированному простому модулю (например, 998244353 = 119·2²³+1). Коэффициенты произведения могут достигать n · (10^9)² ≈ 10^6 · 10^18 = 10^24, что не помещается в один NTT-модуль (~10^9). Обычный FFT с double теряет точность при таких числах.

Решение: многомодульный NTT + КТО.

1. Выбрать три NTT-дружественных простых модуля: M₁ = 998244353, M₂ = 985661441, M₃ = 754974721. Их произведение ≈ 7.4 · 10^26 > 10^24.
2. Выполнить NTT трижды (по каждому модулю) — получить три набора коэффициентов.
3. Для каждого коэффициента восстановить истинное значение через алгоритм Гарнера, взять mod P.

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

// NTT по модулю mod с первообразным корнем g
ll power(ll base, ll exp, ll mod) {
    ll r=1; base%=mod;
    for (; exp>0; exp>>=1) { if (exp&1) r=r*base%mod; base=base*base%mod; }
    return r;
}

void ntt(vector<ll>& a, bool inv, ll mod, ll prim_root) {
    int n = a.size();
    for (int i=1, j=0; i<n; ++i) {
        int bit = n>>1;
        for (; j&bit; bit>>=1) j^=bit;
        j^=bit;
        if (i<j) swap(a[i], a[j]);
    }
    for (int len=2; len<=n; len<<=1) {
        ll w = inv ? power(prim_root, mod-1-(mod-1)/len, mod)
                   : power(prim_root, (mod-1)/len, mod);
        for (int i=0; i<n; i+=len) {
            ll wn=1;
            for (int j=0; j<len/2; ++j) {
                ll u=a[i+j], v=a[i+j+len/2]*wn%mod;
                a[i+j]=(u+v)%mod;
                a[i+j+len/2]=(u-v+mod)%mod;
                wn=wn*w%mod;
            }
        }
    }
    if (inv) {
        ll n_inv = power(n, mod-2, mod);
        for (auto& x : a) x=x*n_inv%mod;
    }
}

vector<ll> poly_mult_mod(vector<ll> a, vector<ll> b, ll mod, ll prim_root) {
    int result_size = a.size() + b.size() - 1;
    int n = 1;
    while (n < result_size) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false, mod, prim_root);
    ntt(b, false, mod, prim_root);
    for (int i=0; i<n; ++i) a[i]=a[i]*b[i]%mod;
    ntt(a, true, mod, prim_root);
    a.resize(result_size);
    return a;
}

// Три NTT-простых с их первообразными корнями
const ll MODS[] = {998244353, 985661441, 754974721};
const ll ROOTS[] = {3, 3, 11};

// Восстановление по алгоритму Гарнера, ответ mod out_mod
ll garner_restore(ll r0, ll r1, ll r2, ll out_mod) {
    auto inv_mod = [](ll a, ll m) {
        ll x, y; /* extended_gcd inline */
        // используем power для простых модулей
        ll r=1; ll base=a%m; ll e=m-2;
        for (; e>0; e>>=1) { if (e&1) r=r*base%m; base=base*base%m; }
        return r;
    };
    ll M1 = MODS[0], M2 = MODS[1], M3 = MODS[2];
    // c0 = r0
    ll c0 = r0;
    // c1 = (r1 - c0) * inv(M1) mod M2
    ll c1 = (r1 - c0%M2 + M2) % M2 * inv_mod(M1, M2) % M2;
    // c2 = (r2 - c0 - c1*M1) * inv(M1*M2) mod M3
    ll tmp = (r2 - c0%M3 + M3) % M3;
    tmp = (tmp - c1%M3 * (M1%M3) % M3 + M3) % M3;
    ll c2 = tmp * inv_mod((lll)M1*M2%M3, M3) % M3;
    // x = c0 + c1*M1 + c2*M1*M2 (mod out_mod)
    ll result = c0 % out_mod;
    result = (result + c1 % out_mod * (M1 % out_mod)) % out_mod;
    result = (result + c2 % out_mod * ((lll)M1%out_mod * (M2%out_mod) % out_mod)) % out_mod;
    return result;
}

vector<ll> poly_mult(vector<ll> a, vector<ll> b, ll out_mod) {
    // NTT по трём модулям
    vector<vector<ll>> res(3);
    for (int i=0; i<3; ++i) res[i] = poly_mult_mod(a, b, MODS[i], ROOTS[i]);

    int sz = res[0].size();
    vector<ll> answer(sz);
    for (int i=0; i<sz; ++i)
        answer[i] = garner_restore(res[0][i], res[1][i], res[2][i], out_mod);
    return answer;
}

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

    const ll OUT_MOD = 1'000'000'007LL;
    int n, m; cin >> n >> m;
    vector<ll> a(n+1), b(m+1);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;

    auto c = poly_mult(a, b, OUT_MOD);
    for (int i=0; i<(int)c.size(); ++i)
        cout << c[i] << " \n"[i+1==(int)c.size()];
    return 0;
}

Почему три модуля достаточно? Коэффициент произведения ≤ (n+1) · (max_coeff)² ≤ 10^6 · (10^9)² = 10^24. Произведение трёх модулей: 998244353 · 985661441 · 754974721 ≈ 7.4 · 10^26 > 10^24. Значит, при восстановлении алгоритм Гарнера однозначно определяет коэффициент.

Сложность: O(n log n) для каждого NTT, O(n) для восстановления. Итого O(n log n).

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

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

1. Переполнение при вычислении lcm.

// Неверно:
ll lcm = m1 * m2;  // переполнение при m1, m2 ~ 10^9
// Верно:
ll g = __gcd(m1, m2);
ll lcm = m1 / g * m2;  // сначала делим, потом умножаем

2. Неверная проверка совместности.

// Неверно: проверяем только gcd(m1, m2) == 1
// Верно: gcd(m1, m2) должен делить (r2 - r1)
if ((r2 - r1) % g != 0) { /* несовместна */ }

3. Знак остатка при вычислении k.

// В C++ оператор % может возвращать отрицательное число!
ll k = x * (diff / g) % step;
k = (k % step + step) % step;  // нормализуем в [0, step)

4. Потеря решения x = 0. Если x₀ = 0 является решением системы, нужно убедиться, что это ожидаемый ответ. При поиске наименьшего положительного нужно взять M (следующее решение).

5. Неправильный порядок в алгоритме Гарнера. Коэффициенты c₀, c₁, c₂ вычисляются последовательно — каждый следующий зависит от предыдущих. Нарушение порядка даёт неверный результат.

6. Использование double при проверке совместности. (r2 - r1) % g должно быть целочисленным. Использование double для проверки кратности — гарантированная ошибка.

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

На практике для NTT выбирайте модули из проверенного списка: 998244353 (примитивный корень 3), 985661441 (корень 3), 469762049 (корень 3). Все они имеют форму c·2^k + 1 и поддерживают NTT до длины 2^23.

Для обобщённой КТО с потенциальными несовместностями всегда проверяйте результат: вычислите x₀ mod каждого mᵢ и убедитесь, что получается aᵢ. Это занимает O(k), но экономит часы отладки на соревнованиях.

Если вам нужно объединять системы онлайн (например, в задаче с запросами), заранее убедитесь, что lcm не растёт за пределы long long. Если модули попарно простые и каждый ≤ 10^6, то lcm ≤ примерно 10^24 — нужна __int128 или большая арифметика.

Итог

Китайская теорема об остатках — это мощный инструмент разложения задачи «найти x по модулю большого M» на k независимых подзадач «найти x по маленьким модулям». Прямая формула с Mᵢ · yᵢ проста и эффективна для взаимно простых модулей. Алгоритм Гарнера нужен, когда произведение M не умещается в машинное слово.

Обобщённая КТО (для нескольких несовместных модулей) требует отдельной проверки делимости и использует lcm вместо произведения. Итеративный подход позволяет решать системы любого размера.

Главное практическое применение для соревновательного программирования — многомодульный NTT, который позволяет честно перемножать большие многочлены с коэффициентами порядка 10^9.