poj2891中国剩余定理（不互质）

/*
Time:2019.12.14
Author: Goven
type：线性同余方程组+中国剩余定理 
ref:
[知识点]
https://blog.csdn.net/u012061345/article/details/80934617
https://blog.csdn.net/tick_tock97/article/details/71313058
https://blog.csdn.net/destiny1507/article/details/81751168
[代码]https://blog.csdn.net/u012061345/article/details/80939440 
*/
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;



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

bool mergeCrt (ll a1, ll c1, ll a2, ll c2, ll &tpa1, ll &tpr1) {
    ll d , x, y;
    ext_gcd(a1, a2, x, y, d);
    ll c = (c2 - c1) % a2;//err1:扩展欧几里得中c必须是 % mod之后的 
    if (c % d) return false;
    x = c / d * x;
    ll mod = a2 / d; mod = mod > 0 ? mod : -mod;
    x = (x % mod + mod) % mod;
    
    tpa1 = a1 / d * a2;
    tpr1 = (x * a1 % tpa1 + c1) % tpa1;
    return true;
    
}

int main()
{
    int k;
    ll a1, r1, a2, r2;
    while (cin >> k) {
        a1 = 1, r1 = 0;
        bool flag = true;
        for (int i = 0; i < k; i++) {
            cin >> a2 >> r2;
            if (flag) {
                flag = mergeCrt(a1, r1, a2, r2, a1, r1);
            }
            
        }
        if (flag) cout << r1 << endl;
        else cout << -1 << endl;
    } 
    return 0;
}