跳转至

威尔逊定理

内容

Wilson 定理

对于素数 .

证明

我们可以利用 同余方程原根 得到两种简洁的证明,此处略去不表。

我们选择介绍前置知识较少的一种证明方法:

时,命题显然成立。

以下设 ,此时我们要证 中所有非零元素的积为 .

我们知道 中所有非零元素 都有逆元 ,于是 中彼此互逆的元素乘积为 .

但是要注意 可能相等。若 ,则 ,即

从而 .

这说明 中所有元素的乘积为 , 进而 中所有非零元素的积为 .

对于整数 ,令 表示所有小于等于 但不能被 整除的正整数的乘积,即 .

Wilson 定理指出 且可被推广至模素数 的幂次。

应用

阶乘与素数

在某些情况下,有必要考虑以某个素数 为模的公式,包含分子和分母中的阶乘,就像在二项式系数公式中遇到的那样。

只有当阶乘同时出现在分数的分子和分母中时,这个问题才有意义。否则,后续项 将减少为零。但在分数中,因子 可以抵消,结果将是非零。

因此,要计算 ,而不考虑阶乘中出现因数 。写下素因子分解,去掉所有因子 ,并计算乘积模。

表示这个修改的因子。例如:

这种修正的阶乘,可用于快速计算各种带取模和组合数的公式的值。

计算余数的算法

计算上述去掉因子 的阶乘模 的余数。

可以清楚地看到,除了最后一个块外,阶乘被划分为几个长度相同的块。

块的主要部分 很容易计算,可以应用 Wilson 定理:

总共有 个块,因此需要将 写到 的指数上。可以注意到结果在 之间切换,因此只需要查看指数的奇偶性,如果是奇数,则乘以 。除了使用乘法,也可以从结果中减去 .

最后一个部分块的值可以在 的时间复杂度单独计算。

这只留下每个块的最后一个元素。如果隐藏已处理的元素,可以看到以下模式:

这也是一个修正的阶乘,只是维数小得多。它是:

因此,在计算修改的阶乘 中,执行了 个操作,剩下的是计算 ,于是有了递归,递归深度为 ,因此算法的总时间复杂度为 .

如果预先计算阶乘 ,那么时间复杂度为 .

计算余数算法的实现

具体实现不需要递归,因为这是尾部递归的情况,因此可以使用迭代轻松实现。在下面的实现中预计算了阶乘 .

因此时间复杂度为 . 如果需要多次调用函数,则可以在函数外部进行预计算,于是计算 的时间复杂度为 .

实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int factmod(int n, int p) {
  vector<int> f(p);
  f[0] = 1;
  for (int i = 1; i < p; i++) f[i] = f[i - 1] * i % p;
  int res = 1;
  while (n > 1) {
    if ((n / p) % 2) res = p - res;
    res = res * f[n % p] % p;
    n /= p;
  }
  return res;
}

如果空间有限,无法存储所有阶乘,也可以只存储需要的阶乘,对它们进行排序,然后计算阶乘 而不显式存储它们。

Legendre 公式

如果想计算二项式系数模 ,那么还需要考虑在 的阶乘的素因子分解中 出现的次数,或在计算修改因子时删除因子 的个数。

Legendre 公式

中含有的素数 的幂次 为:

其中 进制下 的各个数位的和。

特别地,阶乘中 2 的幂次是

证明

记为 那么其中 的倍数有 然后在 中继续寻找 的倍数即可,这是一个递归的过程。

第二个等号与等比数列求和公式很相似。由于涉及各位数字和,利用数学归纳法可以轻松证明。

实现
1
2
3
4
5
6
7
8
int multiplicity_factorial(int n, int p) {
  int count = 0;
  do {
    n /= p;
    count += n;
  } while (n);
  return count;
}

时间复杂度

以下记 .

Kummer 定理

组合数对一个数取模的结果,往往构成分形结构,例如谢尔宾斯基三角形就可以通过组合数模 2 得到。

如果仔细分析, 是否整除组合数其实和上下标在 进制下减法是否需要借位有关。这就有了 Kummer 定理

Kummer 定理

在组合数 中的幂次,恰好是 进制下 减掉 需要借位的次数。

特别地,组合数中 的幂次是 .

Wilson 定理的推广

Wilson 定理的推广

对于素数 和正整数 .

证明

依然考虑配对一个数与其逆元,也就是考虑关于 的同余方程 的根的乘积,当 时方程仅有一根,当 时有四根为 其他时候则有两根为 .

至此我们对 Wilson 定理的推广中的 有了详细的定义,即

下文两个推论中的 ,均特指这样的定义:当模数 及以上的 的幂时取 ,其余取 .

推论 1

对于素数 、正整数 、非负整数

证明

表示不能被 整除的数的乘积,有

记为 就得到了上述第二行。

至此得到了:

推论 2

对于素数 和正整数 和非负整数

其中 与上述相同。

右边的分母中括号内的项均在模 意义下均存在逆元,可直接计算,而 的与上述相同。

例题

例题 HDU 2973 - YAPTCHA

给定 , 计算

解题思路

是质数,则

不是质数,则有 ,即

,则

因此

参考代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

constexpr int M = 1e6 + 5, N = 3 * M + 7;

bool not_prime[N];
int sum[M];

int main() {
  for (int i = 2; i < N; ++i)
    if (!not_prime[i])
      for (int j = 2; j * i < N; ++j) not_prime[j * i] = true;
  for (int i = 1; i < M; ++i) sum[i] = sum[i - 1] + !not_prime[3 * i + 7];

  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::cout << sum[n] << std::endl;
  }
}

本页面主要译自博文 Вычисление факториала по модулю 与其英文翻译版 Factorial modulo p。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。

参考资料

  1. 冯克勤。初等数论及其应用。