/*
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;
}
poj2891中国剩余定理（不互质）
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 中国剩余定理（Chinese Remainder Theorem，CRT）又称孙子定理，是数论中的一个定理。古典数...
