中国剩余定理

「物不知数」问题

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

即求满足以下条件的整数:除以 ,除以 ,除以

该问题最早见于《孙子算经》中,并有该问题的具体解法。宋朝数学家秦九韶于 1247 年《数书九章》卷一、二《大衍类》对「物不知数」问题做出了完整系统的解答。上面具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出:

三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五便得知。

,故答案为

算法简介及过程

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组(其中 两两互质):

上面的「物不知数」问题就是一元线性同余方程组的一个实例。

算法流程

  1. 计算所有模数的积
  2. 对于第 个方程:
    1. 计算
    2. 计算 在模 意义下的 逆元
    3. 计算 不要对 取模)。
  3. 方程组的唯一解为:

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// C++ Version
LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Python Version
def CRT(k, a, r):
    n = 1; ans = 0
    for i in range(1, k + 1):
        n = n * r[i]
    for i in range(1, k + 1):
        m = n // r[i]; b = y = 0
        exgcd(m, r[i], b, y) # b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n
    return (ans % n + n) % n

算法的证明

我们需要证明上面算法计算所得的 对于任意 满足

时,有 ,故 。又有 ,所以我们有:

即对于任意 ,上面算法得到的 总是满足 ,即证明了解同余方程组的算法的正确性。

因为我们没有对输入的 作特殊限制,所以任何一组输入 都对应一个解

另外,若 ,则总存在 使得 在模 下不同余。

故系数列表 与解 之间是一一映射关系,方程组总是有唯一解。

下面演示 CRT 如何解「物不知数」问题。

  1. 三人同行 七十 希:,故
  2. 五树梅花 廿一 支:,故
  3. 七子团圆正 半月,故
  4. 所以方程组的唯一解为 。(除 百零五 便得知)

Garner 算法

CRT 的另一个用途是用一组比较小的质数表示一个大的整数。

例如,若 满足如下线性方程组,且 (其中 为质数):

我们可以用以下形式的式子(称作 的混合基数表示)表示

Garner 算法 将用来计算系数

在模 意义下的

代入我们得到的第一个方程:

代入第二个方程得出:

方程两边减 ,除 后得

类似地,我们可以得到:

参考代码
1
2
3
4
5
6
7
8
9
// C++ Version
for (int i = 0; i < k; ++i) {
  x[i] = a[i];
  for (int j = 0; j < i; ++j) {
    x[i] = r[j][i] * (x[i] - x[j]);
    x[i] = x[i] % p[i];
    if (x[i] < 0) x[i] += p[i];
  }
}
1
2
3
4
5
6
7
8
# Python Version
for i in range(0, k):
    x[i] = a[i]
    for j in range(0, i):
        x[i] = r[j][i] * (x[i] - x[j])
        x[i] = x[i] % p[i]
        if (x[i] < 0):
            x[i] = x[i] + p[i]

该算法的时间复杂度为 。实际上 Garner 算法并不要求模数为质数,只要求模数两两互质,我们有如下伪代码:

可以发现在第六行中的计算过程对应上述混合基数的表示。

应用

某些计数问题或数论问题出于加长代码、增加难度、或者是一些其他原因,给出的模数:不是质数

但是对其质因数分解会发现它没有平方因子,也就是该模数是由一些不重复的质数相乘得到。

那么我们可以分别对这些模数进行计算,最后用 CRT 合并答案。

下面这道题就是一个不错的例子。

洛谷 P2480 [SDOI2010]古代猪文

给出 ),求:

首先,当 时,所求显然为

否则,根据 欧拉定理,可知所求为:

现在考虑如何计算:

因为 不是质数,无法保证 都有逆元存在,上面这个式子我们无法直接计算。

注意到 ,其中每个质因子的最高次数均为一,我们可以考虑分别求出 在模 这几个质数下的结果,最后用中国剩余定理来合并答案。

也就是说,我们实际上要求下面一个线性方程组的解:

而计算一个组合数对较小的质数取模后的结果,可以利用 卢卡斯定理

扩展:模数不互质的情况

两个方程

设两个方程分别是

将它们转化为不定方程:,其中 是整数,则有

由裴蜀定理,当 不能被 整除时,无解;

其他情况下,可以通过扩展欧几里得算法解出来一组可行解

则原来的两方程组成的模方程组的解为 ,其中

多个方程

用上面的方法两两合并即可。

习题


评论