CRT&&EXCRT学习笔记

这是个大坑，今天填了，本来应该好久以前就会的（但硬是没学）

关于CRT

CRT就是中国剩余定理，是一个没什么泛用性但是偶尔会考的东西

（相比之下没怎么考过的欧拉函数就显得比较惨）

其中mi两两互质，求最小的x

首先构造M为所有mi的乘积，然后Mi为M/mi，易得Mi和mi互质，

因此必有bi使Mi*bi = 1（mod mi）即bi为模mi意义下Mi的逆元，

所以可以得到Mi*bi*ai = ai（mod mi）

把所有Mi*bi*ai相加就是一个合法解x（这是一个没有证的东西）

为了使x为最小正整数，所以x还要模mi的LCT（不是指LINK-CUT-TREE）

即x = （x%M+M）%M（因为mi两两互质所以LCT就是M）

愉快。

Luogu P3868 猜数字

裸体板子，式子移个项就是CRT

但是出题人很鹅心，要用龟速乘处理一个爆longlong的点，还有就是要时刻注意逆元的正负和大小

对于一个最小正整数逆元可以x[i] = (x[i]%m[i] + m[i]) % m[i]（相当于调整EXGCD中x和y）

丢人蒟蒻把乘的式子写错了（快滚快滚）

#include<bits/stdc++.h>

using namespace std ;

const int MAXN = 20;
long long K,a[MAXN],Mi[MAXN],M,m[MAXN],ans,x[MAXN];

void exgcd(long long a,long long b,long long &x,long long &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    long long xx=x,yy=y;
    x=yy;
    y=xx-(a/b)*yy;
    return ;
}

long long inv(long long a,long long mod){
    long long xxx=0,y=0;
    exgcd(a,mod,xxx,y);
    return xxx;
}

long long qm(long long a,long long b,long long mod){
    long long ret=0;
    while(b){
        if(b&1) (ret+=a)%=mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>K;
    for(int i=1;i<=K;i++){
        cin>>a[i];
    }
    for(int i=1;i<=K;i++){
        cin>>m[i];
    }
    M=1;
    for(int i=1;i<=K;i++){
        M *= m[i];
    }
    for(int i=1;i<=K;i++){
        Mi[i] = M / m[i];
    }
    for(int i=1;i<=K;i++){
        x[i] = inv(Mi[i],m[i]);
//        cout<<"Mi[i] = "<<Mi[i]<<"m[i] = "<<m[i]<<endl;
//        cout<<"x[i] = "<<x[i]<<endl;
        x[i] = (x[i]%m[i] + m[i]) % m[i];
    }
    for(int i=1;i<=K;i++){
        ans += qm(qm(a[i],Mi[i],M),x[i],M);
        ans %= M;
    }
    
//    cout<<"M = "<<M<<endl;
//    for(int i=1;i<=K;i++){
//        cout<<"m"<<i<<" = "<<m[i]<<"M"<<i<<" = "<<Mi[i]<<" "<<endl;
//    }
//    for(int i=1;i<=K;i++){
//        cout<<"x"<<i<<" = "<<x[i]<<" "<<endl;
//    }
    cout<<ans<<endl;
    return 0;
}
 //凝聚SB气息的调试信息...

这个是CRT，只适用于m两两互质的情况，如果m没有任何特殊条件呢？

这就是EXCRT了

关于EXCRT

把EXCRT要干的的事情用式子写出来就是

其中mi不一定两两互质，求最小的正整数解x

网上看了几个版本，有一种合并的求x方式，同机房几个大佬都写过了，这里不再赘述

但有一种容易理解的写法（niiick的博客），感觉非常好

大概是这样的：

对于第一个式子解为a[1]%m[1]（是啊仔细想想）

如果对于前k-1个式子已经有了一个最小非负整数解x，并且设M为前k-1个m的乘积，

那么对于前k-1个式子来说，所有解x的表达式为 {x(all)} = x + O * M (O为整数)

现在要用这个表达式，找一个解x，使对于前k个式子来说，x = a[i] (mod m[i]) (1<=i<=k)

（我这种暴力选手看到这里直接想向上枚举了，但是经验告诉我们不能乱搞）

可以把对于前k-1个式子都合法的那个x叫做x0（没有Markdown原谅下⑧）

那么我们要求x0 + t * M = a[k] (mod m[k])

　　　　变形为t * M + O * m[k] = a[k] - x0 (O为任意整数系数）

首先判断a[k]-x0是不是gcd(M,m[k])的倍数，不是则整个方程式无解

是则EXGCD求解t，

然后处理t使其最小正整数（与m[k]交易），

然后x += t * M，处理M，接着处理下一个式子

最后全部式子处理完之后得到答案x

也比较愉快。去看题

Luogu P4777 【模板】扩展中国剩余定理（EXCRT）

数据范围比CRT大多了，同时观察到a和b的给出方式利于在线处理

还有一堆小细节要处理，要乘什么，式子表示的是不是对的，

当前系数表示的东西是什么，怎么维护才是正确的

这一步要不要取模，balabala，还有，HAVE FUN DEBUGING

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100010;
long long n,ai[MAXN],bi[MAXN];

long long qm(long long a,long long b,long long mod){
    long long ret=0;
    while (b){
        if(b&1) (ret += a) %= mod;
        a = (a+a) % mod;
        b>>=1;
    }
    return ret;
}

long long  exgcd(long long  a,long long  b,long long  &x,long long  &y) { 
    if(b==0){x=1;y=0;return a;} 
    long long  gcd=exgcd(b,a%b,x,y); 
    long long  tp=x; x=y; y=tp-a/b*y; 
    return gcd;
} 

long long  excrt() { 
     long long x,y,k;
      long long M=bi[1],ans=ai[1];
       for(int i=2;i<=n;i++) { 
           long long  a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;
        long long  gcd=exgcd(a,b,x,y),bg=b/gcd;
//         if(c%gcd!=0) return -1;
          x=qm(x,c/gcd,bg); 
          ans+=x*M; 
          M*=bg; 
          ans=(ans%M+M)%M;
    } 
    return (ans%M+M)%M; 
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>bi[i]>>ai[i];
    }
    cout<<excrt()<<endl;
    return 0;
}

TAG：SIN_XIII ⑨