专栏文章

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 题解

FFish_egg_
P1495题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipym3ia
此快照首次捕获于
2025/12/03 20:04
3 个月前
此快照最后确认于
2025/12/03 20:04
3 个月前
查看原文

中国剩余定理（CRT）\large\color{00aacd}\textbf{中国剩余定理（CRT）}

前置知识：同余、逆元、扩展欧几里得定理。

算法介绍\color{00cd00}\text{算法介绍}

中国剩余定理用于求解如下形式的同余方程组：
{x≡b1(moda1)x≡b2(moda2)…x≡bn(modan)\begin{cases} x\equiv b_1 \pmod{a_1} \\ x\equiv b_2 \pmod{a_2} \\ \dots \\ x\equiv b_n \pmod{a_n} \end{cases}
其中，a1,a2,…ana_1, a_2, \dots a_n 两两互质。
求解的过程如下：
  1. 计算所有模数的积 M=∏i=1naiM = \prod\limits_{i=1}^n a_i。
  2. 依次考虑每一个方程。对于第 ii 个方程：
    • 计算 mi=M÷aim_i = M \div a_i。
    • 计算 mim_i 在模 aia_i 意义下的逆元 mi−1m_i^{-1}。
      • 因为 a1,a2,…,ana_1, a_2, \dots, a_n 两两互质，显然有 gcd⁡(mi,ai)=1\gcd(m_i, a_i) = 1，即逆元一定存在。
  3. 最终，xx 最小的非负整数解为 x=(∑i=1nmi⋅mi−1⋅bi) mod Mx = (\sum\limits_{i=1}^n m_i\cdot m_i^{-1}\cdot b_i) \bmod M。

正确性证明\color{00cd00}\text{正确性证明}

我们需要证明，以上算法所得到的 xx 满足 ∀i∈[1,n], x≡bi(modai)\forall i \in [1, n],\ x\equiv b_i \pmod{a_i}。
根据以上 mim_i 的定义，可以得到当 i≠ji\ne j 时，mj≡0(modai)m_j\equiv 0 \pmod{a_i}。
又根据逆元的定义，可以得到 mi⋅mi−1≡1(modai)m_i \cdot m_i^{-1} \equiv 1 \pmod{a_i}。
因此：
x≡∑j=1nmj⋅mj−1⋅bj(modai)≡mi⋅mi−1⋅bi(modai)≡bi(modai)\begin{aligned} x &\equiv \sum_{j=1}^n m_j\cdot m_j^{-1}\cdot b_j &\pmod{a_i} \\ &\equiv m_i\cdot m_i^{-1}\cdot b_i &\pmod{a_i} \\ &\equiv b_i &\pmod{a_i} \end{aligned}
即：∀i∈[1,n], x≡bi(modai)\forall i \in [1, n],\ x\equiv b_i \pmod{a_i}。算法的正确性得证。

代码实现\color{00cd00}\text{代码实现}

由于 aia_i 不一定是质数，不能用费马小定理求逆元，所以用了扩展欧几里得定理来求。
C++:
本题运算过程中可能会爆 long long，需要使用 __int128 才能通过。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 15;
int n, a[N], b[N];
pair<int, int> exgcd(int a, int b){
	if(b == 0) return {1, 0};
	auto [x, y] = exgcd(b, a % b);
	return {y, x - a / b * y};
}
int inv(int a, int p){
	auto [x, y] = exgcd(a, p);
	return (x + p) % p; //exgcd 求出的解有可能是负的，所以取模一下转成正的
}
int CRT(int n, int *a, int *b){
	int M = 1, x = 0;
	for(int i=1; i<=n; i++) M *= a[i];
	for(int i=1; i<=n; i++){
		__int128 Mi = M / a[i], Ti = inv(Mi, a[i]);
		x = (x + Mi * Ti * b[i] % M) % M;
	}
	return x;
}
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i] >> b[i];
	cout << CRT(n, a, b);
	return 0;
}
Python:
PYTHON
def exgcd(a, b):
    if b == 0: return (1, 0)
    x, y = exgcd(b, a % b)
    return y, x - a // b * y
    
def inv(a, p): return exgcd(a, p)[0] % p

def CRT(n, a, b):
    M = 1; x = 0
    for i in range(n): M *= a[i]
    for i in range(n):
        Mi = M // a[i]; Ti = inv(Mi, a[i])
        x += Mi * Ti * b[i]
    return x % M

def main():
    n = int(input())
    a = [0] * n; b = [0] * n
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    print(CRT(n, a, b))

if __name__ == '__main__':
    main()

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...