首先我們還是從簡單入手，考慮一下如果同餘方程組隻有兩個式子的情況
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