发布时间：2024-10-03

中国剩余定理

概念

• $x \equiv r_1(mod\ m_1)$
• $x \equiv r_2(mod\ m_2)$
• $x \equiv r_n(mod\ m_n)$
• $n=m_1 \cdot m_2 \cdot ...m_n，M_i=\frac{n}{m_i} ,M_i^{-1}为模m_i的逆元$
• $答案为\sum_{i=1}^N r_iM_i^{-1}M_i(mod\ n)$

int CRT(vector<int> &r,vector<int> &m){
    __int128 n=1,ans=0;
    for(auto &x:m)n*=x;
    for(int i=0;i<r.size();i++){
        int M=n/m[i],iM,y;
        exgcd(M,m[i],iM,y);
        (ans+=r[i]%n*M%n*iM%n)%=n;
    }
    return (ans%n+n)%n;
}

拓展中国剩余定理

• 合并$a \equiv r_1(mod\ m_1)和a \equiv r_2(mod\ m_2)$
• $r_1+k_1m_1=r_2+k_2m_2$
• $k_1m_1-k_2m_2=r_2-r_1$
• $d=gcd(m_1,m_2),d|(r_2-r_1)有解$
• $求出 p_1=\frac{m_1}{d},p_2=\frac{m_2}{d},求出\lambda _1p_1+\lambda _2p_2=1的解$
• $k_1=\frac{r_2-r_1}{d}\lambda _1,k_2=-\frac{r_2-r_1}{d}\lambda _2$
• $x=r_1+k_1m_1=r_1+\frac{r_2-r_1}{d} \lambda _1m_1$
• $若有特解x^{*},则 x \equiv x^{*} (mod\ lcm(m_1,m_2))$

int qmul(int a,int b,int mod){
    int ans=0;
    for(;b;b>>=1){
        if(b&1)ans=(ans+a)%mod;
        a=(a+a)%mod;
    }
    return ans;
}
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int exCRT(vector<int> &r,vector<int> &m){
    int r1=r[0],m1=m[0];
    int x,y;
    for(int i=1;i<r.size();i++){
        int r2=r[i],m2=m[i],res=((r2-r1)%m2+m2)%m2;
        int gcd=exgcd(m1,m2,x,y);
        if(res%gcd!=0)return -1;
        x=qmul(x,res/gcd,m2);
        r1+=x*m1;
        m1=m2/gcd*m1;
        r1=(r1%m1+m1)%m1;
    }
    return r1;
}