CRT中国剩余定理

特别版（除数两两互质）

void ex_gcd(int a, int b, int &x, int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }
    else
    {
        int x1, y1;
        ex_gcd(b, a%b, x1, y1);
        if(a*b<0)
        {
            x=-y1;
            y=a/b*y1-x1;
        }
        else
        {
            x=y1;
            y=x1-a/b*y1;
        }
    }
}

ll CRT(int a[], int m[], int len)//a[ ]余数，m[ ]除数
{
    int N[10];
    int lca=1;
    int res=0;
    for(int i=0; i<len; i++)
        lca*=m[i];
    for(int i=0; i<len; i++)
    {
        int L, J;
        ex_gcd(lca/m[i], -m[i], L, J);
        N[i]=J*m[i]+1;
        res+=N[i]*a[i];
    }
    return (res%lca+lca)%lca;
}

普通版（任意情况）
两两合并变成互质情况。

void exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }
    exgcd(b, a%b, x, y);
    ll t=x;
    x=y;
    y=t-(a/b)*y;
    return ;
}

ll CRT(int n)
{
    ll c, d, x, y;
    ll M=m[1], R=r[1];
    for(int i=2; i<=n; i++)
    {
        d=gcd(M, m[i]);
        c=r[i]-R;
        if(c%d) return -1;
        exgcd(M/d, m[i]/d, x, y);
        x=(c/d*x)%(m[i]/d);
        R=R+x*M;
        M=M/d*m[i];
        R%=M;
    }
    if(R<0) R+=M;
    return R;
}