中国剩余定理

具体描述：

给出你n个ai和mi，最后让求出x的最小值是多少。

中国剩余定理说明：假设整数m1, m2, … , mn两两互质，则对任意的整数：a1, a2, … , an，方程组(S)有解，并且通解可以用如下方式构造得到：

数论倒数(number-theoretic reciprocal)亦称算术倒数，是与同余有关的一个基本概念。 设m为模，a为任意整数，且(a，m)=1。 若有整数a′能满足同余式a′a≡1(mod m)，则称a′是a(mod m)的数论倒数，或逆元。

例子:

三个模数m1=3, m2=5, m3=7的乘积是M=105，对应的M1=35, M2=21, M3=15. 而可以计算出相应的数论倒数：t1=2, t2=1, t3=1. 所以《孙子歌诀》中的70，21和15其实是这个“物不知数”问题的基础解：

而将原方程组中的余数相应地乘到这三个基础解上，再加起来，其和就是原方程组的解：

这个和是233，实际上原方程组的通解公式为：

《孙子算经》中实际上给出了最小正整数解，也就是k=-2时的解：x=23.

///n个mi互质
const LL maxn = 20;
LL a[maxn], m[maxn], n;
LL CRT(LL a[], LL m[], LL n)
{
    LL M = 1;
    for (int i = 0; i < n; i++) M *= m[i];
    LL ret = 0;
    for (int i = 0; i < n; i++)
    {
        LL x, y;
        LL tm = M / m[i];
        ex_gcd(tm, m[i], x, y);
        ret = (ret + tm * x * a[i]) % M;
    }
    return (ret + M) % M;
}

---

下面也就是关于这个的扩展，前面我们已经说了，中国剩余数定理是适用于n个mi两两互质的情况的，如果不互质呢，下面就是一个转换：
模不两两互质的同余式组可化为模两两互质的同余式组，再用孙子定理直接求解。

84=22×3×7,160=25×5,63=32×7

///n个mi不互质
const LL maxn = 1000;
LL a[maxn], m[maxn], n;
LL CRT(LL a[], LL m[], LL n) {
    if (n == 1) {
        if (m[0] > a[0]) return a[0];
        else return -1;
    }
    LL x, y, d;
    for (int i = 1; i < n; i++) {
        if (m[i] <= a[i]) return -1;
        d = ex_gcd(m[0], m[i], x, y);
        if ((a[i] - a[0]) % d != 0) return -1;   //不能整除则无解
        LL t = m[i] / d;
        x = ((a[i] - a[0]) / d * x % t + t) % t; //第0个与第i个模线性方程的特解
        a[0] = x * m[0] + a[0];
        m[0] = m[0] * m[i] / d;
        a[0] = (a[0] % m[0] + m[0]) % m[0];
    }
    return a[0];
}