板子 CRT & exCRT

大概写写中国剩余定理的公式和扩展中国剩余定理板子。

中国剩余定理 CRT

对于一元线性同余方程组： \[ \begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ ……\\ x\equiv a_n\pmod{m_n} \end{cases} \] x 的最小非负整数解，其中 \(m_i\) 两两互质。

该方程组的通解为： \[ \begin{aligned} M&=\prod_{i=1}^nm_i\\ M_i&=\frac{M}{m_i}\\ t_i&\equiv M_i^{-1}\pmod{m_i}\\ x&\equiv \sum_{i=1}^n{a_it_iM_i\pmod M} \end{aligned} \]

x 最小的话，\(t_i\) 最小，要在用 exgcd 求解 \(M_i^{-1}\) 时保证 \(t_i\) 最小。

扩展中国剩余定理 exCRT

同样是一元线性同余方程组，不过 \(m_i\) 不再两两互质了。

考虑将方程两两合并。

\[ \begin{cases} x\equiv a\pmod{m}\\ x\equiv A\pmod{M} \end{cases} \] 即 \[ \begin{cases} x=my+a\\ x=MY+A \end{cases} \] \[ \begin{aligned} my+a&=MY+A\\ my-MY&=A-a \end{aligned} \] 通过 exgcd 求出 y 关于 \(my+M(-Y)=\gcd(m,M)\) 的解 \(y_0\)，那么 y 的特定解为 \(y_0\times\frac{A-a}{\gcd(n,M)}\)。

因为要最小化 x，所以要最小化 y。

y 在 exgcd 中通解为 \(y_0+\frac{M}{\gcd(m,M)}\)，所以要最小值为 \[ y=y_0\times\frac{A-a}{\gcd(n,M)}\bmod \frac{M}{\gcd(m,M)} \]

两个同余方程合并为 \[ x\equiv my+a\pmod{\operatorname{lcm}(m,M)} \]

exCRT code

模板题 Luogu P4777

inline LL exCRT() {
    // ai 为 a，bi 为 m
    LL ans = ai[1], mod = bi[1];
    for (int i = 2; i <= n; ++i) {
        LL g, x, y, bg, a = ai[i], b = bi[i], c;
        exgcd(mod, b, x, y, g);
        c = (a - ans % b + b);
        if (c % g) return -1;
        x = mul(x, c/g, b/g); // 防爆long long的快速乘
        ans += x * mod;
        mod = lcm(mod, b);
        ans = (ans % mod + mod) % mod;
    }
    return ans;
}