题目链接：
?id=2891
题目大意：
选择k个不同的正整数a1、a2、…、ak，对于某个整数m分别对ai求余对应整数ri，如果
适当选择a1、a2、…、ak，那么整数m可由整数对组合(ai，，ri)唯一确定。
若已知a1、a2、…、ak以及m，很容易确定所有的整数对(ai，ri)，但是题目是已知a1、
a2、…、ak以及所有的整数对(ai，ri)，求出对应的非负整数m的值。
思路：
题目可以转换为给定一系列的一元线性方程
x≡ r1( mod a1)
x ≡ r2( mod a2)
x = r3( mod a3)
……
x = rk( mod ak)
求解x。就是求解一元线性同余方程组，利用扩展欧几里得算法求解。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;__int64 d,x,y;int N;void ExGCD(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y){if(!b)x = 1, y = 0, d = a;else{ExGCD(b,a%b,d,y,x);y -= x * (a/b);}}__int64 solve(){__int64 a,b,c,a1,r1,a2,r2;bool flag = 1;scanf("%I64d%I64d",&a1,&r1);for(int i = 1; i < N; ++i){scanf("%I64d%I64d",&a2,&r2);a = a1, b = a2, c = r2 – r1;ExGCD(a,b,d,x,y);if(c % d != 0)flag = 0;int t = b/d;x = (x*(c/d)%t + t) % t;r1 = a1 * x + r1;a1 = a1 * (a2 / d);}if( !flag )r1 = -1;return r1;}int main(){while(~scanf("%d",&N)){printf("%I64d\n",solve());}return 0;}
可见内心底对旅行是多么的淡漠。
