1. Идея

Нужно решить систему сравнений вида:

• x ≡ a_1 (mod m_1)
• x ≡ a_2 (mod m_2)
• ...
• x ≡ a_k (mod m_k)

Важная особенность: модули не обязаны быть взаимно простыми. Поэтому обычная форма китайской теоремы об остатках напрямую не подходит.

Идея эталонного решения такая:

• будем последовательно объединять условия;
• после обработки нескольких условий будем хранить одно эквивалентное условие: x ≡ r (mod mod)
• затем попробуем объединить его со следующим условием x ≡ a (mod m)

Если это невозможно, сразу выводим -1.
Если возможно, получаем новое объединённое сравнение и идём дальше.

2. Наблюдения

Наблюдение 1. Что значит объединить два сравнения

Пусть уже есть:

• x ≡ r (mod mod)

Это означает, что все решения имеют вид:

x = r + mod * t

для некоторого целого t.

Теперь нужно ещё выполнить:

• x ≡ a (mod m)

Подставим x = r + mod * t:

r + mod * t ≡ a (mod m)

Переносим r:

mod * t ≡ a - r (mod m)

Получили линейное сравнение относительно t.

Наблюдение 2. Когда решение существует

Сравнение

mod * t ≡ a - r (mod m)

имеет решение тогда и только тогда, когда gcd(mod, m) делит a - r.

Именно это и проверяется в условии:

• g = gcd(mod, m)
• если (a - r) % g != 0, то решения нет.

Наблюдение 3. Как упростить сравнение

Если решение существует, делим всё на g:

• mod1 = mod / g
• m1 = m / g
• rhs = (a - r) / g

Тогда получаем:

mod1 * t ≡ rhs (mod m1)

Теперь mod1 и m1 взаимно просты, потому что общий делитель уже вынесен. Значит, у mod1 существует обратный элемент по модулю m1.

Тогда:

t ≡ rhs * inverse(mod1) (mod m1)

Наблюдение 4. Как получить новое объединённое сравнение

После нахождения подходящего t можно взять:

x = r + mod * t

Это и будет новый остаток.

Новый модуль равен lcm(mod, m), а в коде он вычисляется как:

new_mod = (mod / g) * m

Это то же самое, что НОК.

3. Алгоритм

1. Считываем k.
2. Первое условие (a_1, m_1) принимаем как текущее:
   • r = a_1
   • mod = m_1
3. Для каждого следующего условия (a, m):
   1. Находим g = gcd(mod, m).
   2. Считаем diff = a - r.
   3. Если diff % g != 0, выводим -1 и завершаем программу.
   4. Иначе строим упрощённое сравнение:
      • mod1 = mod / g
      • m1 = m / g
      • rhs = diff / g
   5. Находим обратный элемент к mod1 по модулю m1 с помощью расширенного алгоритма Евклида.
   6. Получаем:
      • t = rhs * inverse(mod1) mod m1
   7. Строим новое решение:
      • new_r = r + mod * t
      • new_mod = mod1 * m
   8. Нормализуем остаток:
      • r = new_r % new_mod
      • если нужно, делаем его неотрицательным.
   9. Обновляем mod = new_mod.
4. После обработки всех условий выводим r.

4. Почему это работает

Докажем корректность последовательного объединения.

Шаг 1. Текущее состояние

Предположим, после обработки нескольких первых условий мы получили эквивалентное сравнение:

x ≡ r (mod mod)

Это означает, что множество всех решений первых условий — ровно все числа вида:

x = r + mod * t

Шаг 2. Добавление нового условия

Теперь добавляем условие:

x ≡ a (mod m)

Подставляя x = r + mod * t, получаем сравнение:

mod * t ≡ a - r (mod m)

Это стандартное линейное сравнение.

Из теории известно:

• оно разрешимо тогда и только тогда, когда gcd(mod, m) делит a - r);
• после деления на g = gcd(mod, m) коэффициент при t становится взаимно простым с новым модулем;
• значит, можно найти обратный элемент и восстановить t.

Именно это делает алгоритм.

Шаг 3. Почему новый остаток верный

Мы находим некоторое значение t, для которого оба условия выполняются, и берём:

x = r + mod * t

Тогда:

• первое сравнение выполняется автоматически, потому что x отличается от r на кратное mod;
• второе выполняется по построению.

Значит, найденный x — общее решение двух сравнений.

Шаг 4. Почему новый модуль равен НОК

Если число удовлетворяет обоим сравнениям, то все такие числа образуют один класс вычетов по модулю lcm(mod, m).

В коде используется:

new_mod = (mod / g) * m

где g = gcd(mod, m). Это и есть lcm(mod, m).

Значит, новое сравнение

x ≡ r (mod new_mod)

точно описывает все общие решения уже обработанных условий.

Шаг 5. Почему последовательное объединение корректно для всей системы

Мы начинаем с первого сравнения, которое очевидно корректно.
На каждом шаге либо:

• обнаруживаем несовместимость и правильно выводим -1,
• либо заменяем систему из уже обработанных сравнений на одно эквивалентное сравнение.

Следовательно, после обработки всех k условий:

• если алгоритм не остановился с -1, то текущее r — наименьшее неотрицательное решение всей системы.

5. Сложность

Пусть k — число условий.

Для каждого нового сравнения выполняются:

• gcd
• расширенный алгоритм Евклида
• несколько арифметических операций

Все они работают за O(log M), где M — величина модулей.

Итоговая сложность:

• O(k log M)

Память:

• O(1), если не считать входные данные.

6. Код на C++17

#include <iostream>
#include <numeric>

using namespace std;

long long exgcd(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 g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long mod_inverse(long long a, long long mod) {
    long long x, y;
    exgcd(a, mod, x, y);
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

int main() {
    int k;
    cin >> k;

    long long r, mod;
    cin >> r >> mod;

    for (int i = 1; i < k; i++) {
        long long a, m;
        cin >> a >> m;

        long long g = gcd(mod, m);
        long long diff = a - r;

        if (diff % g != 0) {
            cout << -1 << '\n';
            return 0;
        }

        long long mod1 = mod / g;
        long long m1 = m / g;
        long long rhs = diff / g;

        long long inv = mod_inverse(mod1 % m1, m1);
        long long t = (rhs % m1 + m1) % m1;
        t = (__int128)t * inv % m1;

        long long new_mod = mod1 * m;
        __int128 new_r = (__int128)r + (__int128)mod * t;
        long long ans = (long long)(new_r % new_mod);
        if (ans < 0) ans += new_mod;

        r = ans;
        mod = new_mod;
    }

    cout << r << '\n';
    return 0;
}

7. Код на Python 3

from math import gcd

k = int(input())
r, mod = map(int, input().split())

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

def mod_inverse(a, mod):
    g, x, y = exgcd(a, mod)
    x %= mod
    return x

for _ in range(k - 1):
    a, m = map(int, input().split())

    g = gcd(mod, m)
    diff = a - r

    if diff % g != 0:
        print(-1)
        break

    mod1 = mod // g
    m1 = m // g
    rhs = diff // g

    inv = mod_inverse(mod1 % m1, m1)
    t = (rhs % m1) * inv % m1

    new_mod = mod1 * m
    r = (r + mod * t) % new_mod
    mod = new_mod
else:
    print(r)