题意

给你一个同余方程组(包含个同余方程)，，让你求的最小非负整数解，无解的情况输出-1

思路

假设，那么

，

可以推出 和 相等，

可以推出 等于 ，

通过拓展欧几里得，我们可以求出 ，那么通解的情况就是 ， 把这个式子代入可以得到，，我们设 等于，那么就得到等于，也就等价于 。

那么为其他的情况，我们就可以两个两个的同余方程消除

代码

/**
 *    author: andif
 *    created: 08.08.2023 22:30:39
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) return x = 1, y = 0, a;
    ll g = exgcd(b, a % b, x, y);
    tie(x, y) = make_tuple(y, x - a / b * y);
    return g;
}

// ll qmul(ll a, ll b, ll mod) {
//     ll ret = 0;
//     while(b) {
//         if (b & 1) {
//             ret = (ret + a) % mod;
//         }
//         a = (a + a) % mod;
//         b >>= 1;
//     }
// }

pll get_ans(const pll& a, const pll& b) {
    pll ret(0, 0);
    auto [p1, r1] = a;
    auto [p2, r2] = b;
    if (r1 < r2) {
        swap(r1, r2);
        swap(p1, p2);
    }
    ll y = -1, x = -1;
    assert(p1 >= 0);
    assert(p2 >= 0);
    ll g = exgcd(p2, p1, y, x);
    // assert(g >= 0);
    // dd(y), dd(p2), dd(p1), dd(x), dd(y * p2 + x * p1), de(g);
    // de(r1 - r2);
    if ((r1 - r2) % g) return ret;
    ret.fi = p1 / g * p2;
    ll d = (r1 - r2) / g;
    ll t = p1 / g * p2;
    // ll y0 = (__int128) y * d;
    // ll x0 = (__int128) y0 * p2 + r2;
    ll x0 = (((__int128) y * d % t * p2) % t + r2) % t;
    // dd(t), dd(x0), dd(x0 % p1), de(x0 % p2);
    if (x0 < 0) {
        x0 = x0 + (-x0 + t - 1) / t * t;
    } else {
        x0 = x0 - (x0 / t) * t;
    }
    // dd(t), dd(x0), dd(x0 % p1), de(x0 % p2);
    ret.se = x0;
    return ret;
}

int main() {
    int n; cin >> n;
    vector<pll> pr(n);
    rep(i, 0, n) cin >> pr[i].fi >> pr[i].se;
    auto ans = pr[0];
    rep(i, 1, n) {
        ans = get_ans(ans, pr[i]);
        if (!ans.fi) break;
    }
    if (!ans.fi) cout << "-1" << '\n';
    else cout << ans.se << '\n';
    return 0;
}