中国剩余定理 CRT 与 exCRT

中国剩余定理

中国剩余定理解决的是这样一类问题：

问题描述

给定 $m$ 个同余方程组：

\begin{cases}x&\equiv a_1\pmod{n_1}\\x&\equiv a_2\pmod{n_2}\\&\vdots\\x&\equiv a_m\pmod{n_m}\\\end{cases}

其中 $n_1,n_2,\dots, n_m$ 两两互质

算法过程

我们可以在 $O(m)$ 的时间内算出 $x$ 的一个解：

计算 $N=\prod_{i=1}^m n_i$
对于第 $i$ 个方程
1. 令 $P_i=\frac{N}{n_i}$
2. 计算 $P_i$ 在 $\mod n_i$ 意义下的逆元 $P_i^{-1}$
3. 计算 $c_i=P_iP_i^{-1}$ （注意不要对 $n_i$ 取模）
最后，一个合法的解是 $x=\sum_{i=1}^m a_ic_i\pmod N$

示例代码

template <typename T = long long>
inline T crt_solve(std::vector<std::pair<T, T>> &eqs) {
    int m = eqs.size();
    T ans = 0, N = 1;
    for (auto [a, n] : eqs) N = N * n;

    for (int i = 0; i < m; i++) {
        auto [a, n] = eqs[i];
        
        T P = N / n;
        auto [g, inv, _] = exgcd(P, n);
        ans = (ans + modmul(modmul(a, P, N), inv, N)) % N;
    }
    return (ans % N + N) % N;
}

中国剩余定理 CRT 与 exCRT

中国剩余定理

拓展中国剩余定理 exCRT