中国剩余定理和拓展中国剩余定理

拓展和非拓展的中国剩余定理的区别在于同余方程组的mod是否两两互质，没有本质区别（个鬼）。

首先用拓展中国剩余定理是完全可以ac中国剩余定理的板题的，但是性能上会差很多，不过应该不会卡这个常数的吧（大雾）

中国剩余定理是很简单的，用拓展欧几里得的板子，加上下面的原理：

很容易出代码，在这里不写了，您可以参见我的一篇叫《求逆元》的博客，里面有详细的介绍。下面讲讲拓展中国剩余定理的原理，证明很简单但是很长，所以只放一个引理。

然后我们就可以把两个方程化成一个。方程越化越少，最后化成一个的时候就胜利了。

出一个拓展中国剩余定理的板子。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define scan(i) scanf("%lld",&i)
 4 using namespace std;
 5 const int maxn=100010;
 6 int n;
 7 ll ai[maxn],bi[maxn];
 8 //mod放在bi里，余数放在ai里 
 9 ll mul(ll a,ll b,ll mod){
10 //返回a*b%mod的值，怕爆long long来着 
11     ll res=0;
12     while(b>0)
13     {
14         if(b&1) res=(res+a)%mod;
15         a=(a+a)%mod;
16         b>>=1;
17     }
18     return res;
19 }
20 ll exgcd(ll a,ll b,ll &x,ll &y){
21 //扩展欧几里得算法，运算结果返回ax+by=gcd(a,b)的特解，存储在x和y中，返回值是gcd(a,b)
22 //上述方程的特解为[x+b/gcd(a,b)t,y+a/gcd(a,b)t],t为任意整数 
23     if(b==0)
24     {
25         x=1,y=0;
26         return a;
27     }
28     ll ret=exgcd(b,a%b,y,x);
29     y-=a/b*x;
30     return ret;
31 }
32 ll excrt(){
33 //有解出结果，无解出-1 
34     ll x,y,k;
35     ll M=bi[1],ans=ai[1];//第一个方程的解特判
36     for(int i=2;i<=n;i++)
37     {
38         ll a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b)
39         ll gcd=exgcd(a,b,x,y),bg=b/gcd;
40         if(c%gcd!=0) return -1; //判断是否无解，然而这题其实不用
41         x=mul(x,c/gcd,bg);
42         ans+=x*M;//更新前k个方程组的答案
43         M*=bg;//M为前k个m的lcm
44         ans=(ans%M+M)%M;
45     }
46     return (ans%M+M)%M;
47 }
48 int main(){
49     scan(n);
50     for(int i=1;i<=n;++i)
51     scan(bi[i]),scan(ai[i]);
52     printf("%lld",excrt());
53     return 0;
54 }