中国剩余定理

中国剩余定理背景

谈到了求解同余方程，那就不得不提 中国剩余定理（Chinese Remainder Theorem）。中国剩余定理又称“孙子定理”，最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做 “物不知数” 问题，原文如下（百度百科提供）：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

中国剩余定理提供了一种在模数互素的情况下解决一组同余方程组的方法，而拓展欧几里得算法可以用来计算模数不互素的情况下的解。

中国剩余定理算法与推导

在中国剩余定理中，假设有一个同余方程组：

\begin{cases} x \equiv a_1 \pmod m_1\\ x \equiv a_2\pmod m_2\\ \vdots\\ x \equiv a_n\pmod m_n \end{cases}

其中， $m_1, m_2, \cdots, m_n$ 两两互质。中国剩余定理告诉我们，以上方程存在唯一的一个解 $x$ ，模数为 $m_1, m_2, \cdots, m_n$ 。

当模数不互素时，我们可以使用拓展欧几里得算法来辅助求解。具体步骤如下：

计算 $M = m_1 \cdot m_2, \cdots, m_n$ 。
对于每一个 $i$ ，计算 $M_i = \frac{M}{m_i}$ 。
对于每个 $i$ ，使用拓展欧几里得算法计算 $M_i$ 在模 $m_i$ 下的逆元 $t_i$ 。
最后的解 $x$ 可以通过如下公式计算： $x = \sum_{i=1}^{n} a_i M_i t_i \mod M$ 。

中国剩余定理代码示例

int chinese_remainder_theorem(const vector<int> &a, const vector<int> &m) {
    int M = 1;
    for (int mi : m) {
        M *= mi;
    }

    int result = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        int ai = a[i];
        int mi = m[i];
        int Mi = M / mi;
        int xi, yi;
        extended_gcd(Mi, mi, xi, yi);
        result = (result + ai * Mi * xi) % M;
    }

    // 保证结果为正
    if (result < 0) {
        result += M;
    }

    return result;
}

其中 a向量和 b向量分别表示余数数组和模数数组。

中国剩余定理背景​

中国剩余定理算法与推导​

中国剩余定理代码示例​

相关引用​

中国剩余定理背景

中国剩余定理算法与推导

中国剩余定理代码示例

相关引用