P4777 【模板】扩展中国剩余定理（EXCRT）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

ll multi(ll a,ll b,ll c) {
    ll ans = 0; a %= c;
    while (b) {
        if (b & 1) ans = (ans + a) % c;
        b >>= 1; a = (a + a) % c;
    }
    return ans;
}

ll extend_CRT(ll a[],ll m[],int n) {
    ll lcm = m[1], ans = a[1], x, y;
    for (int i = 2; i <= n; ++i) {
        ll ai = lcm, mi = m[i], c = (a[i] - ans % mi + mi) % mi;
        ll gcd = extend_gcd(ai, mi, x, y), bg = mi / gcd;
        if(c % gcd != 0) return -1;
        x = multi(x, c / gcd, bg);
        ans += x * lcm; lcm *= bg;
        ans = (ans % lcm + lcm) % lcm;
    }
    return ans;
}

ll a[100005],m[100005];

int main() {
    int n; cin >> n;
    for (int i = 1;i <= n; ++i) {
        scanf("%lld %lld",&m[i],&a[i]);
    }
    cout << extend_CRT(a,m,n) << endl;
    return 0;
}