1. Идея

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

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

Модули m_i не обязаны быть взаимно простыми, поэтому обычная форма китайской теоремы об остатках здесь не подходит напрямую. Нужно использовать общий случай: постепенно объединять сравнения по два.

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

• x ≡ r (mod mod)

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

• x ≡ a (mod m)

Тогда любое число из первого класса имеет вид:

• x = r + mod * t

Подставим это во второе сравнение:

• r + mod * t ≡ a (mod m)

Отсюда:

• mod * t ≡ a - r (mod m)

Это уже одно линейное сравнение относительно t. Его можно решить через gcd и расширенный алгоритм Евклида.

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

Наблюдение 1. Когда два сравнения совместимы

Сравнения

• x ≡ r (mod mod)
• x ≡ a (mod m)

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

Это стандартный критерий совместимости.

Если делимости нет, то ответ сразу -1.

Наблюдение 2. Как свести задачу к нахождению t

Из равенства

• x = r + mod * t

и условия

• x ≡ a (mod m)

получаем:

• mod * t ≡ a - r (mod m)

Обозначим:

• g = gcd(mod, m)

Если a - r делится на g, то можно разделить всё на g:

• (mod / g) * t ≡ (a - r) / g (mod m / g)

Теперь числа mod / g и m / g взаимно просты. Значит, у mod / g существует обратный элемент по модулю m / g.

Наблюдение 3. Зачем нужен расширенный алгоритм Евклида

Чтобы найти обратный элемент к mod / g по модулю m / g, нужно решить:

• (mod / g) * inv ≡ 1 (mod m / g)

Расширенный алгоритм Евклида как раз находит коэффициенты x, y, для которых:

• (mod / g) * x + (m / g) * y = 1

Тогда x и есть обратный элемент по модулю m / g.

Наблюдение 4. Новый модуль после объединения

После объединения двух сравнений получаем новое сравнение:

• x ≡ new_r (mod new_mod)

где

• new_mod = lcm(mod, m) = mod / g * m

Именно этот модуль и используется дальше.

3. Алгоритм

Будем обрабатывать процессы по очереди.

Шаг 1. Инициализация

Считываем первое сравнение и считаем, что текущий ответ:

• x ≡ r (mod mod)

где сначала:

• r = a_1
• mod = m_1

Шаг 2. Последовательно объединяем с каждым следующим условием

Для очередного (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 * inv mod m1
7. Тогда новое решение:
   • new_r = r + mod * t
8. Новый модуль:
   • new_mod = mod1 * m
9. Нормализуем остаток:
   • r = new_r mod new_mod
   • mod = new_mod

Шаг 3. Ответ

После обработки всех процессов число r — это минимальный неотрицательный момент времени, удовлетворяющий всем условиям.

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

Докажем корректность идеи объединения двух сравнений.

Пусть уже известно, что все обработанные ранее условия эквивалентны одному сравнению:

• x ≡ r (mod mod)

Это означает, что все допустимые x имеют вид:

• x = r + mod * t

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

• x ≡ a (mod m)

Подставляем:

• r + mod * t ≡ a (mod m)

то есть

• mod * t ≡ a - r (mod m)

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

Почему проверка diff % g == 0 необходима

Пусть g = gcd(mod, m). Тогда левая часть mod * t всегда делится на g, значит и правая часть a - r тоже должна делиться на g. Если нет, решения не существует.

Почему после деления решение можно найти

Если diff делится на g, то получаем:

• mod1 * t ≡ rhs (mod m1)

где mod1 = mod / g, m1 = m / g, rhs = diff / g.

Теперь gcd(mod1, m1) = 1, поэтому число mod1 обратимо по модулю m1. Значит:

• t ≡ rhs * inv (mod m1)

Так мы находим один подходящий t, а значит и один подходящий x.

Почему новый модуль равен lcm(mod, m)

Все решения двух сравнений образуют один класс по модулю наименьшего общего кратного mod и m. Поэтому после объединения действительно можно хранить систему как:

• x ≡ new_r (mod lcm(mod, m))

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

Почему итоговый r минимален

После каждого шага остаток нормализуется в диапазон от 0 до mod - 1. Поэтому в конце r — минимальный неотрицательный представитель общего класса решений.

5. Сложность

Пусть k — число процессов.

На каждом шаге мы:

• считаем gcd,
• один раз запускаем расширенный алгоритм Евклида.

Обе операции работают за O(log max(mod, m)).

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

• O(k log M), где M — величина модулей.

Память:

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

6. Код на C++17

#include <iostream>
#include <numeric>

using namespace std;

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

long long mod_norm(long long x, long long mod) {
    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 x, y;
        extended_gcd(mod1, m1, x, y);
        long long inv = mod_norm(x, m1);

        long long t = mod_norm((__int128)rhs * inv % m1, m1);
        long long new_mod = mod1 * m;

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

        r = new_r;
        mod = new_mod;
    }

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

7. Код на Python 3

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

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

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

    g = __import__("math").gcd(mod, m)
    diff = a - r

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

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

    _, x, _ = extended_gcd(mod1, m1)
    inv = x % m1

    t = (rhs * inv) % m1
    new_mod = mod1 * m
    r = (r + mod * t) % new_mod
    mod = new_mod

print(r)