中国剩余定理定义：

使用条件

整数$m_1,m_2, … ,m_n$两两互质。
因为用到乘法逆元，乘法逆元的使用条件是：a在模 p 意义下的乘法逆元存在，当且仅当 a和p 互质，在CRT中，求得是$\frac{M}{m_i}$在模$m_i$下的乘法逆元，一开始搞混了，以为条件是$m_i$和$m_i$互质，怎么可能，2个相同的数啊，后来仔细一想，条件应该是$\frac{M}{m_i}$和$m_i$互质，这两个数显然是互质的，这也是为啥CRT要求模数两两互质的原因吧。

模板

自己参考好多代码写的，有问题，请指教。
因为，在oi竞赛都是要最小正解，我就加到代码里了。还有，就是最后就有个$a_i\cdot M_i \cdot t_i$，很容易爆long long，我又把快速乘加进去了，最后干脆把扩欧也加了。总之，一切为了oi。

typedef long long LL;
LL ksc(LL a,LL b,LL p){
    LL res=0;
    while(b){
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}
void exgcd(LL a,LL b,LL &x,LL &y){
    if(!b) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
LL crt(int n,LL *a,LL *m){
    LL M=1,res=0;
    for(int i=1;i<=n;i++) M*=m[i];
    for(int i=1;i<=n;i++){
        LL w=M/m[i],x,y;
        exgcd(w,m[i],x,y);
        x=(x%m[i]+m[i])%m[i];
        res=(res+ksc(ksc(a[i],w,M),x,M))%M;
    }
    return res;
}