发布时间：2024-07-31

拓展中国剩余定理

合并 $ 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)) $

cpp

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;
}

拓展中国剩余定理 ​

拓展中国剩余定理