中国剩余定理

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 6 分钟

参考：百度百科，OI wiki

中国剩余定理背景

中国剩余定理 (Chinese Remainder Theorem, CRT)，又称孙子定理。​

源于中国南北朝时期《孙子算经》的“物不知数”问题：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

题目意思：一个整数分别被3，5，7除时，余数分别为2，3，2，求这个整数

解法歌诀：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知

即

看这个式子还是看不出什么的。让我们仔细地展开看一看。

中国剩余定理陈述

设 是两两互质的正整数。

考虑同余方程组：

同余式： 的意思是整数 除以模数 后，得到的余数等于

解法：

  1. 计算所有模数（除数）的积
  2. 对于第i个方程：
    1. 计算
    2. 计算 在模 意义下的逆元 （即）；
  3. 方程组在模 意义下的唯一解为：．

逆元的算法复习

逆元的直观理解：被除数被除数的逆元模数商

常用算法：

快速幂算法

快速幂算法：pow(a,p-2,p)（python自带函数）。时间复杂度为 。注意只有 是质数时可以用。

线性递推法

可以求出 到 的逆元。显而易见，时间复杂度为。注意只有 是质数时可以用。

扩展欧几里得算法

欧几里得算法，就是刚学c语言时最喜欢的辗转相除法。

1
2
3
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

扩展一下就可以获得扩展欧几里得算法。时间复杂度为 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def gcd(a, b):
    '''
    欧几里得算法
    '''
    if b == 0:
        return a
    return gcd(b, a % b)


def exgcd(a, b):
    '''
    扩展欧几里得算法
    返回 (x, y, g) 满足 a*x + b*y = g = gcd(a, b)
    '''
    if b == 0:
        return 1, 0, a
    x, y, g = exgcd(b, a % b)
    return y, x-a//b*y, g

def mod_inv(a, m):
    x, _, _ = exgcd(a, m)
    return x % m

中国剩余定理计算例题

例题解法：
计算所有模数的积:

计算每个模数排除自己的积：

在模上模数的意义下，算这个积的逆元。
逆元计算过程

答案是233.

中国剩余定理编程例题

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

题目描述

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 头母猪，如果建了 个猪圈，剩下 头猪就没有地方安家了。如果建造了 个猪圈，但是仍然有 头猪没有地方去，然后如果建造了 个猪圈，还有 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入格式

第一行包含一个整数 —— 建立猪圈的次数，接下来 行，每行两个整数 ，表示建立了 个猪圈，有 头猪没有去处。你可以假定 互质。

输出格式

输出包含一个自然数，即为曹冲至少养母猪的数目。

输入输出样例 #1

输入 #1

1
2
3
4
3
3 1
5 1
7 2

输出 #1

1
16

说明/提示

，，

题解

注意题目说了互质，但没有说数是质数。所以要用扩展欧几里得算法来算逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n = int(input())
a = [0 for i in range(n)]  # 猪圈数量，模数
b = [0 for i in range(n)]  # 无家可归的猪猪，余数
a_prod = 1
pigs = 0


def exgcd(a, b):
    if b == 0:
        return 1, 0
    x, y = exgcd(b, a % b)
    return y, x-a//b*y


def mod_inv(a, m):
    x, _ = exgcd(a, m)
    return x % m


for i in range(n):
    a[i], b[i] = map(int, input().split())
    a_prod *= a[i] # 模数的积
for i in range(n):
    m = a_prod//a[i] # 除了该模数的积
    m_inv = mod_inv(m, a[i]) # 求逆元
    pigs = (pigs+b[i]*m*m_inv % a_prod) % a_prod
print(pigs)

扩展中国剩余定理

以上的定理建立在模数互质的情况下，如果不互质的话，进行：

进行两两判断，

合并两个方程的步骤：

  1. 考虑方程组：
  2. 设 ，检查是否有解：当 不能被 整除时，无解。
  3. 若有解，将方程改写为：

    其中 是整数变量。
  4. 得到线性方程：
  5. 使用扩展欧几里得算法求解特解 （实际上只需要 ）：
    • 先解 ，得到一组解 满足
    • 由于 ，原方程的一组特解为：
  6. 则通解为：
  7. 代入 得：
  8. 合并后的新方程为：

    其中 。