『算法-ACM 竞赛-数学-数论』中国剩余定理模板

ACM 常用模板合集

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

int china()
{
    int ans=0,lcm=1,x,y;
    for(int i=1;i<=k;++i) lcm*=b[i];
    for(int i=1;i<=k;++i)
    {
        int tp=lcm/b[i];
        exgcd(tp,b[i],x,y);
        x=(x%b[i]+b[i])%b[i];//x要为最小非负整数解
        ans=(ans+tp*x*a[i])%lcm;
    }
    return (ans+lcm)%lcm;
}

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

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

        x=mul(x,c/gcd,bg);
        ans+=x*M;
        M*=bg;
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}