中国剩余定理

中国剩余定理，\(Chinese Remainder Theorem, CRT\)，用余光求解模数两两互质的一元线性同余方程组。

\(x\equiv a_1(\mod n_1)\)

\(x\equiv a_2(\mod n_2)\)

\(x\equiv a_k(\mod n_k)\)

计算所有模数的积 \(n\).

对于第 \(i\) 个方程，设 \(m_i=\frac{n}{n_i}\)，计算 \(m_i^{-1}(\mod n_i)\)，设\(c_i=m_im_i^{-1}\)，不对 \(n_i\) 取模。

方程组在 \(\mod n\) 下的唯一解为 \(x=\sum_{i=1}^{k}a_ic_i\).

inline int CRT(int k,int a[],int r[]){
    int n=1,ans=0;
    for(int i=1;i<=k;i++)n*=r[i];/*计算所有模数的乘积*/
    for(int i=1;i<=k;i++){
        int m=n/r[i],x,y;/*m mod 其他所有r[i]均为0*/
        exgcd(m,r[i],x,y);/*计算m mod r[i]的逆元x*/
        (ans+=a[i]*m*x%n)%=n;
    }
    return (ans%n+n)%n;
}

证明\(x\equiv a_i(\mod n_i)\).

当 \(i\not=j\) 时，\(m_j\equiv 0(\mod n_i),c_j\equiv m_j\equiv 0(\mod n_i)\).

\(c_i\equiv m_im_i^{-1}(\mod n_i)\equiv 1(\mod n_i)\).

\(x\equiv \sum_{j=1}^{k}a_jc_j(\mod n_i)\equiv a_ic_i(\mod n_i)\equiv a_i(\mod n_i)\).