python/TangDou/AcWing/CRT/204.cpp

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

const int N = 100010;
int a[N], m[N];
int n;
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int exCRT() { // m代表合并多少次，有n个方程，其实m=n-1
    int a1 = a[1], m1 = m[1], a2, m2, k1, k2;

    for (int i = 2; i <= n; i++) { // a1,m1：做为先遣军，准备与后续的方程合并
        a2 = a[i], m2 = m[i];
        int d = exgcd(a1, -a2, k1, k2); // 扩展欧几里得求方程特解,x有用，y无用
        if ((m2 - m1) % d) return -1;   // 拼出来的同余方程无解，继续不下去
        k1 *= (m2 - m1) / d;            // 同比扩大指定倍数
        int t = abs(a2 / d);            // 最小累计单元
        k1 = (k1 % t + t) % t;          // 取得最小正整数解，否则可以会在计算过程中爆long long
        m1 = k1 * a1 + m1;              // 准备下一轮的m[1],a[1]
        a1 = abs(a1 / d * a2);          // 两个顺序不能反
    }
    return (m1 % a1 + a1) % a1; // 取得最小正整数解
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> m[i];
    cout << exCRT() << endl;
}