Reference: http://www.cnblogs.com/ka200812/archive/2011/09/02/2164404.html
之前说过中国剩余定理传统解法的条件是m[i]两两互质，所以这题就不能用传统解法了= =
其实还有种方法：
先来看只有两个式子的方程组：
c≡b1 (mod a1)
c≡b2 (mod a2)
变形得c=a1*x+b1，c=a2*x+b2
a1*x-a2*y=b2-b1
可以用扩展欧几里得求出x和y，进而求出c
那么多个式子呢？可以两个两个的迭代求。
比如上面两个式子求完了，求出一个c，不妨先把它记作c1
c1满足上面两式，但对于所有的式子就不一定都满足了。
因此我们把一个新同余式加入方程组：c≡c1 (mod lcm(a1,a2)) //lcm为最小公倍数
然后依次往下迭代就行了。最后解出的c1就是最终解。
如何判断无解？
对于相邻的两行a1、a2、r1、r2，若 (r2-r1) mod (gcd(a1,a2))!=0说明无解
1 #include "iostream" 2 using namespace std; 3 __int64 a[1000]; 4 __int64 r[1000]; 5 int n; 6 7 __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y){ 8 if (b==0){ 9 x=1;y=0;10 return a;11 }12 else{13 __int64 r=extend_gcd(b,a%b,y,x);14 y=y-x*(a/b);15 return r;16 }17 }18 19 __int64 gcd(__int64 a,__int64 b)20 {21 if (b==0) return a;22 return gcd(b,a%b);23 }24 25 __int64 lcm(__int64 a,__int64 b)26 {27 __int64 tm=gcd(a,b);28 if (tm==0) return 0;29 else return (a*b/tm);30 }31 32 int main()33 {34 while (cin>>n)35 {36 for (int i=1;i<=n;i++)37 cin>>a[i]>>r[i];38 39 __int64 x,y,x1,c1;40 bool sol=true;41 for (int i=2;i<=n;i++)42 {43 __int64 a1=a[i-1],r1=r[i-1];44 __int64 a2=a[i],r2=r[i];45 __int64 tmp=gcd(a1,a2);46 if ((r2-r1)%tmp!=0) sol=false; //此处有个问题= =原来我是这样写的，WA了47 __int64 tm=extend_gcd(a1,a2,x,y); //__int64 tm=extend_gcd(a1,-a2,x,y)48 x1=x*((r2-r1)/tm); //but the original equation is a1*x1-a2*x2=b2-b149 __int64 rq=a2/tm; //__int64 rq=-a2/tm 50 x1=(x1%rq+rq)%rq; //去掉a2的负号就A了，What a fuck！！！51 //个人猜想是因为gcd(a,b)和gcd(a,-b)结果是一样的，52 //而且此处需要的是非负解，结果就YY对了53 c1=a1*x1+r1;54 r[i]=c1;55 a[i]=lcm(a1,a2);56 // cout< <<" "< <
至于负号那个地方有个题hdu 1576，和本题一个情况。把负号YY掉就对了= =