写这个类型博客的目的就是想总结一下某个专题的知识点，方便以后比赛前复习，由于太菜，如有错误，还请斧正。

中国剩余定理又称孙子定理，简单来说是解决两两互质同余问题的最小非负整数解

在模下的解是唯一的，解为

 

 

 

其中，而为模的逆元。

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

int china()
{
    int ans=0,lcm=1,x,y;
    for(int i=1;i<=k;++i) lcm*=b[i];
    for(int i=1;i<=k;++i)
    {
        int tp=lcm/b[i];
        exgcd(tp,b[i],x,y);
        x=(x%b[i]+b[i])%b[i];//x要为最小非负整数解
        ans=(ans+tp*x*a[i])%lcm;
    }
    return (ans+lcm)%lcm;
}

至于扩展中国剩余定理就是对于不一定两两互质的整数的最小非负整数解

这种情况就采用两两合并的思想，假设要合并如下两个方程：

　　那么得到：

　　我们需要求出一个最小的xx使它满足：

　　那么x1x1和x2x2就要尽可能的小，于是我们用扩展欧几里得算法求出x1x1的最小正整数解，将它代回a1+m1x1a1+m1x1，得到xx的一个特解x′x′，当然也是最小正整数解。

　　所以xx的通解一定是x′x′加上lcm(m1,m2)∗klcm(m1,m2)∗k，这样才能保证xx模m1m1和m2m2的余数是a1a1和a2a2。由此，我们把这个x′x′当做新的方程的余数，把lcm(m1,m2)lcm(m1,m2)当做新的方程的模数。（这一段是关键）

　　合并完成：


const LL MAXN = 1e6 + 10;
LL K, C[MAXN], M[MAXN], x, y;
LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {x = 1, y = 0; return a;}
    LL r = exgcd(b, a % b, x, y), tmp;
    tmp = x; x = y; y = tmp - (a / b) * y;
    return r;
}
LL inv(LL a, LL b) {
    LL r = exgcd(a, b, x, y);
    while (x < 0) x += b;
    return x;
}
void solve() 
{
    while (~scanf("%lld", &K)) {
        for (LL i = 1; i <= K; i++) scanf("%lld%lld", &M[i], &C[i]);
        bool flag = 1;
        for (LL i = 2; i <= K; i++) {
            LL M1 = M[i - 1], M2 = M[i], C2 = C[i], C1 = C[i - 1], T = gcd(M1, M2);
            if ((C2 - C1) % T != 0) {flag = 0; break;}
            M[i] = (M1 * M2) / T;
            C[i] = ( inv( M1 / T , M2 / T ) * (C2 - C1) / T ) % (M2 / T) * M1 + C1;
            C[i] = (C[i] % M[i] + M[i]) % M[i];
        }
        printf("%lld\n", flag ? C[K] : -1);
    }
}

（以上参考自https://www.cnblogs.com/MashiroSky/p/5918158.html以及https://blog.csdn.net/niiick/article/details/80229217）