思路和Y总略有不同

由于本题中ai已经不再满足两两互质的性质，那么一般的中国剩余定理就不再适用。
假设我么已经求出前k-1个方程的解x, 记M = lcm(a1, a2, …, ak - 1);
那么满足前k方程个解一定满足x + Mt (t为正整数)
那么求解第k的方程就等价于求 x + tM 同余 mk (模ak)这就是一个线性同余方程，按照扩展欧几里得算法求解即可。
因此我们只用n次扩展欧几里得即可得出答案。

#include <iostream>
#include <cstring>

#define int long long

using namespace std;

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

signed main()
{
    int n, res, M;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int ai, mi;
        cin >> mi >> ai;
        if(!i)
        {
            res = ai % mi;
            M = mi;
        }
        else
        {
            int x, y;
            int d = exgcd(M, mi, x, y);
            int k = ai - res;
            if(k % d)
            {
                res = -1;
                break;
            }
            int mod = mi / d;
            x *= k / d;
            x = (x % mod + mod) % mod; //注意这里必须要取模，或者x = x % mod也行 ，如果不进行范围缩小可能会溢出
            res += x * M;
            d = exgcd(M, mi, x, y);
            M = M * mi / d;
        }
    }
    if(res != -1)cout << res % M << endl;
    else cout << res << endl;
    return 0;
}