题解 | #【模板】扩展中国剩余定理#

【扩展中国剩余定理】

直接套excrt的板子。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

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

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int lcm(int a, int b) { return a / gcd(a, b) * b; }

int excrt(int k, int *a, int *r) {
    int M = r[1], ans = a[1];
    for (int i = 2; i <= k; i++) {
        int x0, y0;
        int c = a[i] - ans;
        int g = exgcd(M, r[i], x0, y0);
        if (c % g != 0) return -1;
        x0 = (__int128)x0 * (c / g) % (r[i] / g);
        ans = x0 * M + ans;
        M = lcm(M, r[i]);
        ans = (ans % M + M) % M;
    }
    return ans;
}

int n, a[N], b[N];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    int res = excrt(n, b, a);
    cout << res;

    return 0;
}