中国剩余定理

一、中国剩余定理（CRT）

求解同余方程组

$$ \left\{ \begin{aligned} & x \equiv a_1 \ (\bmod \ m_1) \\ & x \equiv a_2 \ (\bmod \ m_2) \\ & \dots \\ & x \equiv a_n \ (\bmod \ m_n) \end{aligned} \right. $$

其中 $m_1,m_2,\dots,m_n$ 为两两互素的整数。

1.求解

记 $$M=\prod\limits_{i=1}^n m_i$$ 即 $M$ 为所有 $m_i$ 的最小公倍数
记 $$M_i=\frac{M}{m_i}$$ 即 $M_i$ 为除 $m_i$ 外所有 $m$ 的倍数
记 $t_i$ 为 $M_i$ 的逆元，即 $$t_iM_i \equiv 1 \ (\bmod \ m_i)$$
可构造出该方程的特解为 $$x=\sum\limits_{i=1}^n a_it_iM_i$$
则通解为 $$x=kM+\sum\limits_{i=1}^n a_it_iM_i,k \in \mathbb{Z}$$

2.证明

因为$$\forall \ i,j \in [1,n],i \neq j$$ 有 $$(m_i,m_j)=1$$
所以$$(M_i,m_i)=1$$
所以 $\exists \ t_i$ 使得 $$t_iM_i \equiv 1 \ (\bmod \ m_i)$$
所以$$a_it_iM_i \equiv a_i \ (\bmod \ m_i)$$
而 $\forall \ j \in [1,n],i \neq j$ 满足 $$a_it_iM_i \equiv 0 \ (\bmod \ m_j)$$
所以$\forall \ i \in [1,n]$有$$\sum\limits_{i=1}^n a_it_iM_i \equiv a_i \ (\bmod \ m_i)$$
另外，若 $x_1,x_2$ 均为该方程组的解
所以$\forall \ i \in [1,n]$ 有 $$x_1-x_2 \equiv 0 \ (\bmod \ m_i)$$
又 $m_i$ 两两互素
所以$$M \mid x_1-x_2$$
所以方程任意两解间必然相差 $M$ 的整数倍。

3.实现

对于 $t_iM_i \equiv 1 \ (\bmod \ m_i)$ 可用扩展欧几里得算法求解。

void exgcd(int a,int b,int& x,int& y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    int t=x;
    x=y;
    y=t-x/y*y;
}
inline int crt(){
    int M=1,res=0,Mi,x,y;
    for(int i=1;i<=n;i++)
        M*=m[i];
    for(int i=1;i<=n;i++){
        Mi=M/m[i];
        exgcd(Mi,m[i],x,y);
        (x%=m[i]+=m[i])%=m[i];
        (res+=a[i]*x*Mi)%=M;
    }
    return res<0?res+M:res;
}

二、扩展中国剩余定理（exCRT）

求解同余方程组

$$ \left\{ \begin{aligned} & x \equiv a_1 \ (\bmod \ m_1) \\ & x \equiv a_2 \ (\bmod \ m_2) \\ & \dots \\ & x \equiv a_n \ (\bmod \ m_n) \end{aligned} \right. $$

其中 $m_1,m_2,\dots,m_n$ 为不一定两两互素的整数，求 $x$ 的最小非负整数解。

1.求解

假设已经求出前 $k-1$ 个方程组成的同余方程组的特解为 $x$ ，且有 $$M=\prod\limits_{i=1}^{k-1} m_i$$
则其通解为 $$x+tM,t \in \mathbb{Z}$$
对于第 $k$ 个方程，需要求满足 $$x+tM \equiv a_k \ (\bmod \ m_k)$$ 的正整数 $t$
此同余方程可用扩展欧几里得算法求解
当任意一个同余方程无解时，该同余方程组无解；否则，前 $k$ 个方程组成的同余方程组的特解为 $$x'=x+tM$$
由数学归纳法，该同余方程组的特解可通过 $n$ 次扩展欧几里得算法求得

int exgcd(int a,int b,int& x,int& y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
inline int excrt(){
    int M=m[1],ans=a[1],g,x,y,c;
    for(int i=2;i<=n;i++){
        c=(a[i]-ans%m[i]+m[i])%m[i];
        g=exgcd(M,m[i],x,y);
        if(c%g!=0)
            return -1;
        x=mul(x,c/g,m[i]/g);
        ans+=x*M;
        M*=m[i]/g;
        ((ans%=M)+=M)%=M;
    }
    return ((ans%=M)+=M)%=M;
}