思路与算法

维护已合并解x≡a (mod M)，初始a0,M1。加入x≡b (mod m)，写x=a+Mt，得到Mt≡b−a (mod m)。令g=gcd(M,m)；g不整除差则无解，否则扩欧求逆，得到t模m/g的解。更新a到新周期lcm(M,m)内最小非负代表。

正确性说明

线性同余Mt≡b−a可解当且仅当g整除差。除g后两个系数互质，扩欧给出的逆元求得唯一t模m/g；代回后所有公解恰形成周期M·m/g。归一化a不改变同余类且给出最小非负值。对约束逐个归纳，最终代表恰为全部方程的最小非负解。

复杂度

每条约束扩欧O(log(max(M,m)))，本修订M≤10^18；n条总O(n log10^18)，空间O(log10^18)递归栈，除输入流外不保存全部约束。

易错点

模数不必互质；无解后仍须读完本组输入。源正/非负冲突已统一非负，全部余数0输出0。差可负，要数学取模归一化；乘法用128位，最终周期保证≤10^18。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using I = __int128_t;
ll egcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll u, v, g = egcd(b, a % b, u, v);
    x = v;
    y = u - (a / b) * v;
    return g;
}
ll norm(I a, ll m) {
    a %= m;
    if (a < 0)
        a += m;
    return (ll)a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        ll a = 0, M = 1;
        bool ok = true;
        for (int i = 0; i < n; i++) {
            ll m, b;
            cin >> m >> b;
            if (!ok)
                continue;
            ll u, v, g = egcd(M, m, u, v);
            if ((b - a) % g) {
                ok = false;
                continue;
            }
            ll q = m / g, k = norm((I)((b - a) / g) * u, q), L = (ll)((I)M * q);
            a = norm((I)a + (I)M * k, L);
            M = L;
        }
        cout << (ok ? a : -1) << '\n';
    }
}