首先我们还是从简单入手，考虑一下如果同余方程组只有两个式子的情况
x≡c1(mod m1)
x≡c2(mod m2)
将两个式子变形
x=c1+m1k1
x=c2+m2k2
联立
c1+m1k1=c2+m2k2
移项
m1k1=c2−c1+m2k2
我们用GCD(a,b)表示a,b的最大公约数
在这里需要注意，这个方程有解的条件是
GCD(m1,m2)|(c2−c1)，因为后面会用到(c2−c1)/(m2,m1)这一项，如果不整除的话肯定会出现小数。
推广一下
我们每次把两个同余式合并，求解之后得到一个新的同余式。再把新的同余式和其他的联立，最终就可以求出满足条件的解
题目： https://ac.nowcoder.com/acm/contest/75/B
代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 ll a[100003],b[100003];
4 ll t;
5 void ex(ll x1,ll y1,ll &d,ll &x,ll &y)
6 {
7 if(y1==0)
8 {
9 d=x1;
10 x=1;
11 y=0;
12 return ;
13 }
14 ex(y1,x1%y1,d,y,x);
15 y-=x1/y1*x;
16 }
17 ll china()
18 {
19 ll m1=a[1];
20 ll r1=b[1];
21 for(ll i=2;i<=t;i++)
22 {
23 ll m2=a[i];
24 ll r2=b[i];
25 ll x,y,d;
26 ex(m1,m2,d,x,y);
27 ll r=r2-r1;
28 if(r%d)return -1;
29 ll t=m2/d;
30 x=(x*r/d%t+t)%t;
31 r1=x*m1+r1;
32 m1=m1*m2/d;
33 }
34 if(1==t&&r1==0)return m1;
35 return r1;
36 }
37 int main()
38 {
39 cin>>t;
40 for(ll i=1;i<=t;i++)
41 {
42 cin>>a[i]>>b[i];
43 }
44 cout<<china()<<endl;
45 } View Code