中国剩余定理

首先我们还是从简单入手，考虑一下如果同余方程组只有两个式子的情况

$x \equiv c_{1} (m o d m_{1}) x \equiv c_{2} (m o d m_{2})$

将两个式子变形

$x = c_{1} + m_{1} k_{1} x = c_{2} + m_{2} k_{2}$

联立

$c_{1} + m_{1} k_{1} = c_{2} + m_{2} k_{2}$

移项

$m_{1} k_{1} = c_{2} - c_{1} + m_{2} k_{2}$

我们用GCD $(a, b)$

在这里需要注意，这个方程有解的条件是

$(m_{1}, m_{2}) | (c_{2} - c_{1})$

推广一下

我们每次把两个同余式合并，求解之后得到一个新的同余式。再把新的同余式和其他的联立，最终就可以求出满足条件的解

题目： 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