中国剩余定理学习笔记-526互联

中国剩余定理(CRT)

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 \(m_1, m_2, m_3,\cdots\) 两两互质）：

\[\left\{ \begin{array}{rcl} x \equiv a_1 \bmod m_1 \\ x \equiv a_2 \bmod m_2 \\ x \equiv a_3 \bmod m_3 \\ \cdots \\ x \equiv a_n \bmod m_n \\ \end{array}\right. \]

——oi-wiki

其中，著名的韩信点兵~~(小学奥数题)~~就是上面形式的方程。

那么，如何求解这个问题呢？

首先，注意到如果 \(x_0\) 是原方程的一个整数解，那么 \(x_0 + k \times lcm(m_1, m_2, \cdots, m_n) (k \in \mathbb{Z})\) 也是原方程的整数解；同时，原方程每一个整数解都可写成上述形式。（证明：设 \(x_0, x_1\)均为原方程整数解， \(\forall 0 \leq i \leq n\)，若 \(x_0 \equiv x_1 \bmod m_i\)，则有\(x_0 - x_1 \equiv 0 \bmod m_i\)，故 \(lcm(\{m_i\})\mid x_0 - x_1\) 这意味着，我们只需找到原方程的一个解，便可以求出原方程的最小正整数解了。

为构造出满足要求的解，我们考虑 \(x\) 形如 \(\displaystyle{\sum_{i=1}^nb_i}\)，且 \(b_i \equiv a_i \bmod m_i\)，同时当 \(j \ne i\) 时，\(m_i\mid b_j\)。容易验证这时 \(x\) 合法。

由于当 \(j \ne i\) 时，\(m_j\mid \cfrac{lcm(\{m_i\}}{m_i}\)，故可以考虑将 \(b_i\) 乘上一个 \(\cfrac{lcm(\{m_i\}}{m_i}\)。下面只需满足 \(b_i \equiv a_i \bmod m_i\)。

设 \(inv_i\) 是 \(\cfrac{lcm(\{m_i\}}{m_i}\) 在模 \(m_i\) 意义下的逆元，那么就有 \(inv_i \times \cfrac{lcm(\{m_i\}}{m_i} \times a_i \equiv a_i \bmod m_i\)，同时当 \(j \ne i\) 时，\(m_j\mid inv_i \times \cfrac{lcm(\{m_i\}}{m_i} \times a_i\) 。这样就构造出了 \(b_i\)，进而原方程的其它解也可求出。

求逆元时可以用 exgcd，（快速幂只能在模数为素数时使用，而 exgcd 只要求两数互质。

例题：[洛谷P1495](P1495 [模板]中国剩余定理（CRT）/ 曹冲养猪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

模板题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
typedef pair<int, int> pii;

//#define LOCAL
namespace debug{
    template<typename T, typename... Ts>
    void print(T arg1, Ts... arg_left){
        #ifdef LOCAL
        cerr << arg1 << " ";
        if constexpr (sizeof...(arg_left) > 0) { // c++17
            print(arg_left...);
        }
        else cerr << "\n";
        #endif
    }

}
#define rep(i, j, k) for (int i = (j); i < (k); i++)
#define repd(i, j, k) for (int i = (j); i > (k); i--)
#define repo(i, j) for (; i < (j); i++)
#define repdo(i, j) for (; i > (j); i--)

const int N = 10 + 10;
int n;
int a[N], b[N];
LL pi = 1;
LL p[N], inv[N];
void exgcd(LL a, LL b, LL &x, LL &y){
    if (b == 0){
        x = 1, y = 0;
        return;    
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
} // exgcd 求逆元
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    rep (i, 0, n) {
        cin >> a[i] >> b[i];
        pi *= a[i];
    }
    rep (i, 0, n) {
        p[i] = pi / a[i];
    }
    rep (i, 0, n) {
        LL u = p[i], v = a[i], w, o;
        exgcd(u, v, w, o);
        w = (w + v) % v;
        inv[i] = w;
    }
    LL ans = 0;
    rep (i, 0, n) {
        ans += inv[i] * p[i] * b[i];
    }
    cout << (ans + pi) % pi << '\n';
    return 0;
}

526互联

中国剩余定理 学习笔记

中国剩余定理学习笔记