扩展中国剩余定理

问题

对于同余方程组\(x \equiv a_i(mod \ m_i)\)，其中\(m_i\)为不一定两两互质的整数，求x的最小非负整数解。

求解

假设已经求出前k-1个方程组成的同余方程组的一个解为x，且M是\(m_1\)~\(m_{k-1}\)的最小公倍数。则前k-1个方程的方程组通解为\(x+iM(i∈Z)\)。那么对于加入第k个方程后的方程组，我们就是要求一个正整数t，使得\(x+tM \equiv a_k(mod \ m_k)\)。转化一下上述式子得\(tM \equiv a_k-x(mod \ m_k)\)。对于这个式子我们已经可以通过扩展欧几里得求解t。若该同余式无解，则整个方程组无解；若有，则前k个同余式组成的方程组的一个解为\(x_k=x+tM\)。

所以整个算法的思路就是求解k次扩展欧几里得。

//扩展欧几里得
void ex_gcd(ll a, ll b, ll& d, ll& x, ll& y) {
    if (!b) {
        d = a, x = 1, y = 0;
    }
    else {
        ex_gcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}

//扩展中国剩余定理（非互质） x%a[i]=r[i]
//注意这里的符号含义和上面文字部分不同
ll Chinaa(int len, ll* a, ll* r) {
    ll M = a[0], R = r[0], x, y, d;
    for (int i = 1; i < len; i++) {
        ex_gcd(M, a[i], d, x, y);
        if ((R - r[i]) % d != 0) return -1;
        x = (R - r[i]) / d * x % a[i];
        R -= x * M;
        M = M / d * a[i];
        R %= M;
    }
    return (R % M + M) % M;
}