CRT

9.CRT

CRT可描述如下，其中模数\(n_1,n_2,n_3,...,n_k\)互质

\(\left\{\begin{aligned} x & \equiv a_{1}\left(\bmod n_{1}\right) \\ x & \equiv a_{2}\left(\bmod n_{2}\right) \\ & \vdots \\ x & \equiv a_{k}\left(\bmod n_{k}\right) \end{aligned}\right.\)

定义\(n=\Pi_{i=1}^{k}{n_i}\)，则在模n意义下x有唯一解

记\(m_i=\frac{n}{n_i},m_i^{-1}\)为\(m_i\)在模\(n_i\)意义下的逆元

\(x=\sum_{i=1}^{k}{a_i\times{m_i}}\times{m_i^{-1}}(mod\,n)\)

证明：

把解带回去易得到是正确的

代码：

#include <bits/stdc++.h>

using namespace std;

vector<int> a,n;

int exgcd(int a,int b,int& x,int& y){
    int x1=1,x2=0,x3=0,x4=1;
    while(b){
        int q=a/b;
        tie(a,b,x1,x2,x3,x4)=make_tuple(b,a-q*b,x3,x4,x1-x3*q,x2-x4*q);
    }
    x=x1,y=x2;
    return a;
}

int CRT(vector<int> a,vector<int> n){
    int n_pro=1,ret=0;
    for(int i=0;i<a.size();++i){n_pro*=n[i];}
    for(int i=0;i<a.size();++i){
        int m=n_pro/n[i];
        int m_inv,y;
        exgcd(m,n[i],m_inv,y);
        ret=(ret+a[i]*m*m_inv%n_pro)%n_pro;
    }
    return (ret%n_pro+n_pro)%n_pro;
}

int main(){
    a={2,3,2};
    n={3,5,7};
    cout<<CRT(a,n)<<endl;
    return 0;
}

拓展：Garner算法，模数不互质（考虑两个方程的时候，写出显式，求exgcd，多个方程就是两两合并）

中国剩余定理 - OI Wiki (oi-wiki.org)