威尔逊定理

1 威尔逊定理

内容：
对于素数 $p$ 有 $(p - 1)! \equiv - 1 (\mod p) .$

推论：
$(p - 1)! \equiv 0 (m o d$ $p), (p > 4 \land p$ 为合数 $)$

计算余数算法:

实现 $n!$ % $p$ .

时间复杂度： 时间复杂度为 $O (p + \log_{p} n)$ . 如果需要多次调用函数，则可以在函数外部进行预计算，于是计算 $(n!)_{p}$ 的时间复杂度为 $O (\log_{p} n) .$

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;
}

2 $L e g e n d r e$ 公式:

$n!$ 中含有的素数 $p$ 的幂次 $v_{p} (n!)$ 为：

$v_{p} (n!) = \sum_{i = 1}^{\infty} ⌊ \frac{n}{p^{i}} ⌋ = \frac{n - S_{p} (n)}{p - 1}$
其中 $S_{p} (n)$ 为 $p$ 进制下 $n$ 的各个数位的和。

特别地，阶乘中 2 的幂次是 $v_{2} (n!) = n - S_{2} (n) .$

$O (l o g n)$ 实现：

int multiplicity_factorial(int n, int p) {
  int count = 0;
  do {
    n /= p;
    count += n;
  } while (n);
  return count;
}

3 $K u m m e r$ 定理:

$p$ 在组合数
$(\binom{m}{n})$ 中的幂次，恰好是 $p$ 进制下 $m$ 减掉 $n$ 需要借位的次数。

即
$v_{p} ((\binom{m}{n})) = \frac{S_{p} (n) + S_{p} (m - n) - S_{p} (m)}{p - 1}$

特别地，组合数中 2 的幂次是
$v_{2} ((\binom{m}{n})) = S_{2} (n) + S_{2} (m - n) - S_{2} (m) .$

4 $W i l s o n$ 定理的推广:

对于素数 $p$ 和正整数 $q$ 有 $(p^{q}!)_{p} \equiv \pm 1 (\mod p^{q}) .$

(p^{q}!)_{p} \equiv {\begin{cases} 1, & (p = 2) \land (q \geq 3), \\ - 1, & otherwise . \end{cases}

1 威尔逊定理

2 Legendre 公式:

3 Kummer 定理:

4 Wilson 定理的推广:

2 $L e g e n d r e$ 公式:

3 $K u m m e r$ 定理:

4 $W i l s o n$ 定理的推广: