发布时间：2024-07-31

中国剩余定理

• $ x \equiv r_1(mod\ m_1) $
• $ x \equiv r_2(mod\ m_2) $
• $ x \equiv r_n(mod\ m_n) $
• $ n=m_1 \cdot m_2 \cdot ...m_n，M_i=\frac{n}{m_i} ,M_i^{-1}为模r_i的逆元$
• $ 答案为\sum_{i=1}^N r_iM_i^{-1}M_i(mod\ n) $

int CRT(vector<int> &r,vector<int> &m){
    __int128 n=1,ans=0;
    for(auto &x:m)n*=x;
    for(int i=0;i<r.size();i++){
        int M=n/m[i],iM,y;
        exgcd(M,m[i],iM,y);
        (ans+=r[i]%n*M%n*iM%n)%=n;
    }
    return (ans%n+n)%n;
}