|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
const int N = 100009;
|
|
|
|
|
|
//洛谷P4777 【模板】扩展中国剩余定理（EXCRT）
|
|
|
|
|
|
|
|
|
|
|
|
LL n; // n组数据
|
|
|
|
|
|
LL mod[N], yu[N]; //每组测试数据中，模记为mod[i],余数记为yu[i]
|
|
|
|
|
|
|
|
|
|
|
|
//龟速乘
|
|
|
|
|
|
LL qmul(LL a, LL k, LL b) {
|
|
|
|
|
|
LL res = 0;
|
|
|
|
|
|
while (k) {
|
|
|
|
|
|
if (k & 1) res = (res + a) % b;
|
|
|
|
|
|
a = (a + a) % b;
|
|
|
|
|
|
k >>= 1;
|
|
|
|
|
|
}
|
|
|
|
|
|
return res;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//扩展欧几里得
|
|
|
|
|
|
LL exgcd(LL a, LL b, LL &x, LL &y) {
|
|
|
|
|
|
if (!b) {
|
|
|
|
|
|
x = 1, y = 0;
|
|
|
|
|
|
return a;
|
|
|
|
|
|
}
|
|
|
|
|
|
LL d = exgcd(b, a % b, y, x);
|
|
|
|
|
|
y -= a / b * x;
|
|
|
|
|
|
return d;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//最小公倍数
|
|
|
|
|
|
LL lcm(LL a, LL b) {
|
|
|
|
|
|
LL x, y;
|
|
|
|
|
|
LL d = exgcd(a, b, x, y);
|
|
|
|
|
|
return (a / d * b);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//扩展中国剩余定理
|
|
|
|
|
|
LL excrt() {
|
|
|
|
|
|
LL M = mod[1], ans = yu[1];
|
|
|
|
|
|
// M为前i-1个数的最小公倍数,即lcm(mod[1],mod[2],...,mod[n])
|
|
|
|
|
|
// ans为前i-1个方程的通解
|
|
|
|
|
|
LL x, y;
|
|
|
|
|
|
for (int i = 2; i <= n; i++) {
|
|
|
|
|
|
LL m = mod[i]; //当前要合并方程的模
|
|
|
|
|
|
LL res = (yu[i] - ans % m + m) % m; // r2-r1，之所以%mi,是为了防止余数差出现负数
|
|
|
|
|
|
LL d = exgcd(M, m, x, y); // 1、求特解x0; 2、求最大公约数d
|
|
|
|
|
|
if (res % d) return -1; //无解的情况
|
|
|
|
|
|
LL t = qmul(x, res / d, m); //根据ax+by=1的特解翻番得到方程ax+by=c的特解
|
|
|
|
|
|
ans += t * M; //获得前i个方程的通解 r=r + x*lcm(m1,m2,..)
|
|
|
|
|
|
M = lcm(M, m); //更改M的值,把mi也加到M中去，相当于不断的取所有mi的最小公倍数
|
|
|
|
|
|
ans = (ans % M + M) % M; //对最小公倍数取模就是最小的合理解
|
|
|
|
|
|
}
|
|
|
|
|
|
return ans;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
ios::sync_with_stdio(false); //加速cin和cout
|
|
|
|
|
|
cin >> n;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) cin >> mod[i] >> yu[i];
|
|
|
|
|
|
cout << excrt() << endl;
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
