POJ 2891 Strange Way to Express Integers 中国剩余定理的一般情况

题目地址：http://poj.org/problem?id=2891

思路：http://blog.csdn.net/qq_34446253/article/details/52192786

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
LL gcdEx(LL a,LL b,LL& x,LL& y)
{   //求ax+by=gcd(a,b) 的整数解 返回gcd(a,b); if(b==0) {x=1; y=0; return a;}LL x1,y1;LL gcd=gcdEx(b,a%b,x1,y1);x=y1;y=x1-a/b*y1;return gcd;
}int main()
{int k;LL a,x,y,n,a1,n1,ok,lcm,u0,d;;while(scanf("%lld",&k)!=EOF){	ok=1;cin>>n>>a;for(int i=1;i<k;i++){cin>>n1>>a1;if(!ok) continue;d=gcdEx(n,n1,x,y);if((a1-a)%d) {ok=0;continue;}lcm=n/d*n1;u0=(a-a1)/d*x%n1;   //n1*x + n2*y = (a-a1) 的一个解u0 ,别忘记%n1 a=(a-u0*n)%lcm;  //合并a n=lcm;           //合并n }if(ok) cout<<(a%n+n)%n<<endl; //最后只有一个式子x≡a(mod n)求出最小解 else printf("-1\n");}return 0;
}