$\Huge\color{orchid}{点击此处获取更多干货}$

中国剩余定理及其扩展

假设有$n$个方程组成了下面的线性同余方程组：
$\left\{\begin{matrix}x\equiv a_1(mod~m_1) \\x\equiv a_2(mod~m_2) \\… \\x\equiv a_n(mod~m_n)\end{matrix}\right.$
那么当所有的模数$m_i$互质时，该方程组的解为$x\equiv \sum_{i=1}^{n}a_i*M_i*M_i^{-1}(mod ~M)$，其中$M=\prod_{i=1}^{n}m_i$，$M_i=M/m_i$，$M_i^{-1}$是$M_i$在模$m_i$意义下的逆元，这就是中国剩余定理$\text{(CRT)}$的描述。

但是$\text{CRT}$有一个刚需条件那就是所有模数互质，因为模数不互质的时候，$M_i$和$m_i$不一定互质了，有可能求不出$M_i^{-1}$，这时候就需要扩展中国剩余定理$\text{(exCRT)}$登场：对于方程组内任意两个方程$x\equiv a_1(mod~m_1)$和$x\equiv a_2(mod~m_2)$，如果它们有解$x_0$，则所有的$x$一定满足$x\equiv x_0(mod~lcm(m_1,m_2))$，这意味着原方程组里的两个方程可以在一定条件下合并为一个方程。所以最关键的就是判断这些方程能否两两合并，即找出满足表达式的$x_0$。

上述两方程可以转化为$k_1*m_1-k_2*m_2=a_2-a_1$，由裴蜀定理可知，如果$(a_2-a_1)\%gcd(m_1, m_2)\neq 0$，则方程无解，无法合并，否则就可以利用$exGCD$算法求出$(k_1,k_2)$，求解过程如下：

在可合并，并且已经求出$\lambda_1,\lambda_2$的情况下，合并而成的方程为$x\equiv (a_1+(a_2-a_1)*\lambda_1*m_1/d)\%L(mod~L)$，其中$L=lcm(m_1, m_2)$即$m_1*m_2/gcd(m_1,m_2)$，由于不保证被取模的数非负，因此实际取模时应为$(x\%L+L)\%L$

C++代码

（代码为理论推演，实测如有偏差，后续会修正）

/**
 * @param n 方程组中方程的个数
 * @param a,m 每个方程x=a(mod m)中的系数a和m
 * @return 方程组的最小正整数解
 * @retval -1 无解
 */
_LL exCrt(int n, _LL* a, _LL* m) {
    _LL a1 = a[0], m1 = m[0];                           //第一个方程的系数
    for (int i = 1; i < n; i++) {
        _LL a2 = a[i], m2 = m[i],                       //从第二个方程开始，依次往第一个方程上合并
            lambda1, lambda2;                           //用于后续求k
        _LL gcd = exGcd(m1, m2, lambda1, lambda2);      //第一次exGCD，仅用于求gcd(m1,m2)
        if ((a2 - a1) % gcd != 0) return -1;            //裴蜀定理
        exGcd(m1 / gcd, m2 / gcd, lambda1, lambda2);    //第二次exGCD，求出中间值lambda
        _LL lcm = m1 * m2 / gcd,
            k = (a2 - a1) * lambda1 / gcd;              //用lambda求出k
        a1 = ((a1 + k * m1) % lcm + lcm) % lcm;         //不保证a1+k*m1非负，需要多次累加取模以保证非负
        m1 = lcm;                                       //合并后方程的系数继续成为a1,m1
    }
    return a1;                                          
}