中国剩余定理及其拓展 CRT&EXGCD

今天药忘吃喽~ 2021-11-22 05:02 363阅读 0赞

中国剩余定理，又叫孙子定理。

作为一个梗广为流传。其实它的学名叫中国单身狗定理。

*  中国剩余定理

中国剩余定理是来干什么用的呢？

其实就是用来解同余方程组的。那么什么又是同余方程组呢。

顾名思义就是n个同余方程。

形如![1706483-20190628144654428-539106582.png][]

如果只有一个方程的话那么是很容易用exgcd来解决。

但如果变成n个就需要用到CRT了。

下面我们言归正传。

首先我们要知道只有满足m1，m2，mn两两互质才能运用CRT。

首先，我们令M=Πni=1。

令Mi=M/mi，这样我们就可以满足Mi%mk=0（k！=i）。

然后我们在构造n个数，对于每一个数ti满足Mi×ti≡1（mod mi），即ti为Mi在mod mi意义下的乘法逆元（好像是这么叫吧），用exgcd可求。

最后再把所有Mi×ti×ai求和再取模就可以了。

为什么这样做是正确的呢？因为Mi×ti≡1（mod mi），则Mi×ti×ai≡ai（mod mi）。

显然，把所有的数加到一起必定满足方程。（切记不要忘了取模）。

一道模板题LOJ10212

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <cmath>
     5 #include <queue>
     6 #include <vector>
     7 using namespace std;
     8 int m[1005], a[1005];
     9 long long qpow(long long a, long long b) {
    10     long long ans = 1;
    11     while (b) {
    12         if (b & 1)
    13             ans = ans * a;
    14         b = b >> 1;
    15         a = a * a;
    16     }
    17     return ans;
    18 }
    19 long long exgcd(long long a, long long b, long long &x, long long &y) {
    20     long long t;
    21     if (!b) {
    22         x = 1;
    23         y = 0;
    24         return a;
    25     }
    26     long long gcd = exgcd(b, a % b, x, y);
    27     t = x;
    28     x = y;
    29     y = t - a / b * y;
    30     return gcd;
    31 }
    32 int main() {
    33     int n;
    34     long long M = 1;
    35     scanf("%d", &n);
    36     for (int i = 1; i <= n; i++) {
    37         scanf("%d%d", &m[i], &a[i]);
    38         M *= 1ll * m[i];
    39     }
    40     long long ans = 0;
    41     for (int i = 1; i <= n; i++) {
    42         long long x, y;
    43         long long Mi = M / m[i];
    44         exgcd(Mi, m[i], x, y);
    45         ans += x * Mi * a[i];
    46     }
    47     printf("%lld", (ans % M + M) % M);
    48 }

CRT

*  拓展中国剩余定理

在上面CRT讲解中我们提到所有的m必须两两互质，因为如果不两两互质就可能无解或求错。

但是如果毒瘤出题人就让他们不互质呢。

那我们就需要把出题人吊起来打一顿用到拓展CRT（实际上他和CRT没有任何关系）

首先只考虑有两个方程怎么做

x=a1\+k1×m1，x=a2\+k2×m2 。可以得到k2×m2-k1×m1=a1-a2。

嗯，看起来有点像一个二元一次方程了。

我们令 gcd=gcd（m1，m2），c=a1-a2;

如果gcd%c！=0则无解

否则用exgcd来求出k1×m1+k2×m2=gcd的解k1，再乘上c/gcd就好了。

为了避免爆long long 最好取一下模。

这样我们就可以反推出x。

但注意我们解的方程k1项系数为-1，相当与k1=-k1（所以k1=0？）

这样就求出了x。（可以把这个x0转化成最小的非负数解）  
　　这个x符合第一个方程，也符合第二个方程。设这个x为x0  
　　所以，可以得到通解是：x=x0+k×lcm(m1,m2)　　  
　　满足这个条件的x就满足第一第二两个方程。满足第一第二两个方程的所有的解也都是这个方程的解。  
　　所以第一第二个方程和这个方程是等价的。  
　　将这个方程转化一下，可以得到新的同余方程：x=x0(modlcm(m1,m2))  
　　这样，我们成功的把两个方程转化成了一个方程，以此类推。  
　　最后留下的这个方程，它的x\_0的最小非负数解，就是我们要的最终答案（最后这一段用文本编辑器打的，略显不符，请自动忽略）。

例题 poj2891

模板题，直接放代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<vector>
     6 #include<cstdlib>
     7 using namespace std;
     8 #define int long long
     9 int m[100005],c[100005];
    10 int exgcd(int a,int b,int &x,int &y){
    11     int t;
    12     if(!b){
    13         x=1;y=0;
    14         return a;
    15     }
    16     int gcd=exgcd(b,a%b,x,y);
    17     t=x;
    18     x=y;
    19     y=t-a/b*y;
    20     return gcd;
    21 }
    22 signed main(){
    23     int n;
    24     while(~scanf("%lld",&n)){
    25         bool ju=1;
    26         for(int i=1;i<=n;i++) scanf("%lld%lld",&m[i],&c[i]);
    27         int m1=m[1],c1=c[1];
    28         for(int i=2;i<=n;i++){
    29             int x,y;
    30             int m2=m[i],c2=c[i];
    31             int dembele=exgcd(m1,m2,x,y);
    32             if((c2-c1)%dembele){
    33                 ju=0;
    34                 printf("-1\n");
    35                 break;
    36             }
    37             x=(c1-c2)/dembele*x%m2;
    38             c1-=m1*x;
    39             m1=m1/dembele*m2;
    40             c1%=m1;
    41         }
    42         if(ju)
    43         printf("%lld\n",(c1%m1+m1)%m1);
    44     }
    45 }

EXCRT

转载于:https://www.cnblogs.com/leom10/p/11102890.html

[1706483-20190628144654428-539106582.png]: /images/20211122/791d3ba6a3d94b549e80496fd618dcd6.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/c03f3ce3112b479c977a81c8baae0bdd.png