问题

求满足： \[ \begin{aligned} x &\equiv b_1 &\pmod{a_1} \\ x &\equiv b_2 &\pmod{a_2} \\ x &\equiv b_3 &\pmod{a_3} \\ &\ \ \vdots &\\ x &\equiv b_n &\pmod{a_n} \end{aligned} \] 的 \(x\) 的值。

ExCRT

当 \(a_1, a_2, \cdots, a_n\) 互素的时候显然可以使用中国剩余定理（CRT）解决，时间复杂度为 \(O(n\log n)\)。

考虑不互素的情况，假设已经解决了前 \(i - 1\) 个方程，得到的解为 \(x_{i - 1}\)，\(\operatorname{lcm}(a_1, \cdots, a_{i - 1}) = m\)。

那么我们考虑解决 \[ x_{i - 1} + tm \equiv b_i \pmod{a_i} \] 易证得到的解 \(x_i = x_{i - 1} + tm\) 不会再和前 \(i\) 个解产生冲突。

稍微移项一下： \[ tm \equiv b_i - x_{i - 1} \pmod{a_i} \] 用 ExGCD 解出 \(t\) 即可。

这套方法称为 ExCRT（拓展中国剩余定理），复杂度依旧是 \(O(n\log n)\)。全面优于 CRT。

代码：

#include <cstdio>

using namespace std;
typedef long long ll;
const int N = 100010;
int n;
ll a[N], b[N];

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

ll smul(ll x, ll y, ll mod) {
    if (y < 0) return -qmul(x, -y, mod);
    ll ret = 0;
    for (; y; y >>= 1) {
        if (y & 1) ret = (ret + x) % mod;
        x = (x + x) % mod;
    }
    return ret;
}

ll excrt() {
    ll lcm = a[1], t = b[1], x, y;
    for (int i = 2; i <= n; i++) {
        ll d = exgcd(lcm, a[i], x, y);
        x = smul(x, (b[i] - t) / d, a[i]);
        t += x * lcm;
        lcm = lcm / d * a[i];
        t = (t % lcm + lcm) % lcm;
    }
    return t;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
    printf("%lld\n", excrt());
    return 0;
}