[数论] 中国剩余定理

· · 个人记录

//后台卡崩 迫于生计重敲

对于 同余方程组 x \equiv a_i \pmod {b_{i}}

设 前 k-1 组方程的最小非负整数解为 ans

M = \operatorname{lcm}(b_{1},…,b_{k-1})

则 前 k-1 组方程的通解为 ans + t * M (t \in N)

对于 第k个方程 即求解 t

ans + t * M \equiv a_{k} \pmod b_k

整理得到

M * t + b_{k} * y = a_{k} - ans

对于上述不定方程 使用 exgcd模板 求解即可

对于 M_{k} 的求法 只需要 \frac{b_{k}}{\gcd(M,b_{k})} * M 即可

ll an[N],bn[N];
ll ans=1,x,y,M=1;
ll exgcd(ll a,ll b)
{
    ll d;
    if(b)
    {
        d=exgcd(b,a%b);
        ll t=x;
        x=y,y=t-a/b*y;
    }
    else
        x=1,y=0,d=a;
    return d;
}
for(int i=1;i<=n;i++)
{
    ll a=M,b=bn[i];
    ll d=exgcd(a,b),m=b/d;
    ll c=((an[i]-ans)%b+b)%b;
    x=x*(c/d)%m;
    ans+=x*M;
    M*=m;
    ans=(ans%M+M)%M;
}

放大 x 和 用 M_k 调整 ans

当然可以 从 i = 2 开始

个人喜欢 一个完整的循环……