中国剩余定理及其扩展

中国剩余定理

假如给定一组同余方程：

\[\begin{cases} x \equiv a_1 \text{mod} m_1 \\ x \equiv a_2 \text{mod} m_2 \\ \vdots \\ x \equiv a_k \text{mod} m_k \end{cases}\]

其中 \(m_1, m_2, \ldots, m_k\) 两两互质，下面介绍如何求解该组方程。

我们令 \(M = m_1 \cdot m_2 \cdots m_k\)，并且对于每个 \(i\)，定义 \(M_i = \frac{M}{m_i}\)。由于 \(m_i\) 和 \(M_i\) 互质，可以知道 \(M_i\) 在模 \(m_i\) 意义下是有逆元的，记为 \(M_i^{-1}\)。不难发现 \(M_i \cdot M_i^{-1} \equiv 1 \text{mod} m_i\) 和 \(M_i \cdot M_i^{-1} \equiv 0 \text{mod} m_j\)（\(j \neq i\)）都成立。记 \(c_i = a_i \cdot M_i \cdot M_i^{-1}\)，则有：

\[\begin{cases} c_i \equiv a_i \text{mod} m_i \\ n_i \equiv 0 \text{mod} m_j \quad (j \neq i) \end{cases}\]

由同余的线性性质可知，\(x' = \sum_{i=1}^{k} c_i\) 即为一个特解。

不难证明通解可以写成 \(x = x' + t \cdot M \quad (t \in \mathbb{Z})\)。

注意在上述的过程中，我们要求解 \(M_i\) 在模 \(m_i\) 意义下的逆元，只有在 \(m_i\) 两两互质的情况下才能保证每次求解的逆元存在。

代码如下：

template <typename T>
static void crt(const std::vector<T> &a, const std::vector<T> &m, T &x, T &l) {
    assert(a.size() == m.size());
    x = 0;
    l = 1;
    for (auto &&e : m) { l *= e; }
    for (int i = 0; i < a.size(); i++) {
        x = (x + a[i] * (l / m[i]) % l * inverse_of(l / m[i], m[i]) % l) % l;
    }
}

扩展中国剩余定理

扩展中国剩余定理是在中国剩余定理的基础上，放宽了对模数的互质要求。假设给定一组同余方程：

\[\begin{cases} x \equiv a_1 \text{mod} m_1 \\ x \equiv a_2 \text{mod} m_2 \\ \vdots \\ x \equiv a_k \text{mod} m_k \end{cases}\]

并不保证 \(m_1, m_2, \ldots, m_k\) 两两互质，下面介绍如何求解该组方程。

不难发现，\(x = x' + t \cdot M \quad (t \in \mathbb{Z})\) 是同余方程 \(x \equiv x' \text{mod}{M}\) 的解。

假设我们已经求出了前 \(i-1\) 个方程的解：

\[x = x_{i-1} + t \cdot M_{i-1} \quad (t \in \mathbb{Z}),\]

现在考虑如何求其与

\[x \equiv a_i \text{mod}{m_i}\]

的公共解。

将当前的解代入上述方程，得到：

\[x_{i-1} + t \cdot M_{i-1} \equiv a_i \text{mod}{m_i},\]

即

\[t \cdot M_{i-1} \equiv a_i - x_{i-1} \text{mod}{m_i}.\]

设 \(d = \gcd(M_{i-1}, m_i)\)，则上式有解的充要条件是\(d \mid (a_i - x_{i-1})\)。

如果有解，将上式两边同时除以 \(d\)，得到：

\[t \cdot \frac{M_{i-1}}{d} \equiv \frac{a_i - x_{i-1}}{d} \text{mod}{\frac{m_i}{d}}.\]

由于\(\frac{M_{i-1}}{d}\)和\(\frac{m_i}{d}\)互质，可以用扩展欧几里得算法求该方程的一个特解 \(t_0\)，则通解可以表示为：

\[t = t_0 + k \cdot \frac{m_i}{d} \quad (k \in \mathbb{Z}).\]

将通解代入\(x = x_{i-1} + t \cdot M_{i-1}\)中，可以得到：

\[x = x_{i-1} + t_0 \cdot M_{i-1} + k \cdot \frac{m_i}{d} \cdot M_{i-1} \quad (k \in \mathbb{Z}).\]

因此，新的解可以表示为：

\[x = x_i + k \cdot M_i \quad (k \in \mathbb{Z}),\]

其中

\[\begin{cases} x_i = x_{i-1} + t_0 \cdot M_{i-1} \\ M_i = \frac{m_i}{d} \cdot M_{i-1} \end{cases}\]

特别地，我们可以增加一个方程 \(x \equiv 0 \text{mod} 1\) 作为初始条件，此时 \(x_0 = 0\)，\(M_0 = 1\)。这里给出代码：

template <typename T>
static void ex_crt(const std::vector<T> &a, const std::vector<T> &m, T &x, T &l) {
    x = 0;
    l = 1;
    for (int i = 0; i < a.size(); i++) {
        T t0, _;
        T d = gcd(l, m[i]);
        if ((a[i] - x) % d != 0) {
            x = l = -1;
            return;
        }
        ex_gcd(l / d, m[i] / d, t0, _);
        t0 = (a[i] - x) / d * t0 % (m[i] / d);
        t0 = (t0 % (m[i] / d) + (m[i] / d)) % (m[i] / d);
        x = x + t0 * l;
        l = m[i] / d * l;
        x %= l;
    }
}

中国剩余定理

扩展中国剩余定理

Enjoy Reading This Article?