扩展中国剩余定理

重点
1. 如何根据裴蜀定理，求x=k1a1+m1, x=k2a2+m2的方程的可行最小正整数x解
2. 如果存在解，那么解的表达式是什么，k1=k1+ka2/d
3. 将k1通解代入方程，得出x的表达式，据此推出这两个方程的解的新表达式，并继续和下一个方程做计算
4.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

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

int main() {
    int n;
    LL a2, m2, a1, m1, k1, k2;
    cin >> n;
    cin >> a1 >> m1;
    int flag = true;
    for (int i = 0; i < n - 1; i++) {
        cin >> a2 >> m2;
        LL d = exgcd(a1, a2, k1, k2);
        if ((m2 - m1) % d) {
            flag = false;
            break;
        }
        k1 = k1 * (m2 - m1) / d;  // 将方程右侧化成m2-m1
        LL t = a2 / d;   // k1的通解=k1 + k*a2/d
        k1 = (k1 % t + t) % t;  // 将k1化成最小正整数
        m1 = k1 * a1 + m1;  //先算m1，否则a1是下一个方程的系数
        a1 = abs(a2 / d * a1);
    }
    //LL x = k1 * a1 + m1;
    if (flag) cout << (m1 % a1 + a1) % a1 << endl;  // 求最小正整数解
    else cout << -1 << endl;

    return 0;
}