[模板] 扩展中国剩余定理

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

int n;
ll a1, b1;

ll (ll x, ll y) {
    if (!y) return x;
    return gcd(y, x%y);
}

ll mul(ll x, ll y, ll mod) {
    ll t = y, ret = 0;
    for (int i = 0; i < 63; i++) {
        if (x & (1ll<<i))
            ret = (ret + t) % mod;
        t = t*2%mod;
    }
    return ret;
}

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

int main() {
    scanf("%d", &n);
    a1 = 1; b1 = 0;
    for (int i = 1; i <= n; i++) {
        ll a2, b2;
        scanf("%lld%lld", &a2, &b2);
        ll na = a1/gcd(a1,a2)*a2;
        ll x, y;
        exgcd(a1, -a2, x, y);
        ll k = (b2-b1)/gcd(a1,-a2);
        int t = 1;
        if (k < 0) {
            k = -k; 
            t = -t;
        }
        if (x < 0) {
            x = -x;
            t = -t;
        }
        ll k1 = t*mul(k, x, na);
        k1 %= na;
        if (k1 < 0) k1 += na;
        b1 = (mul(k1%na, a1, na)+b1)%na;
        a1 = na;
    }
    printf("%lldn", b1);
    return 0;
}