威尔逊定理（Wilson 定理）

内容

对于素数 $p$ 有

$$(p-1) ! \equiv-1(\bmod p)$$

对于整数 $n$ ，令 $(n!)_p$ 表示所有小于等于 $n$ 但不能被 $p$ 整除的正整数的乘积，即

$$(n !)_p=n ! /\left(\lfloor n / p\rfloor ! p^{\lfloor n / p\rfloor}\right)$$

威尔逊定理指出 $(p !)_p=(p-1) ! \equiv-1 \pmod{p}$ 且可被推广至模素数 $p$ 的幂次。

---

应用

1. 阶乘 & 素数

（这一段我本来想直接搬 oiwiki 的文本的，然而这 oiwiki 怕不是机翻的）

在某些情况下需要考虑以素数 $p$ 为模数的公式，而且是含有分子和分母都含有阶乘的某些分式

考虑用 $p$ 的幂次的形式表示 $(n!)_p$ ，如下

$$\begin{aligned} (n !)_p= & 1 \times 2 \times 3 \times \cdots \times(p-2) \times(p-1) \times \underbrace{1}_p \times(p+1) \times(p+2) \times \cdots \times(2 p-1) \times \underbrace{2}_{2 p} \\ & \times(2 p+1) \times \cdots \times\left(p^2-1\right) \times \underbrace{1}_{p^2} \times\left(p^2+1\right) \times \cdots \times n \pmod{p} \\ = & 1 \times 2 \times 3 \times \cdots \times(p-2) \times(p-1) \times \underbrace{1}_p \times 1 \times 2 \times \cdots \times(p-1) \times \underbrace{2}_{2 p} \times 1 \times 2 \\ & \times \cdots \times(p-1) \times \underbrace{1}_{p^2} \times 1 \times 2 \times \cdots \times(n \bmod p) \pmod{p} \end{aligned}$$

吐槽：oiwiki 的 $\cdot \ldots \cdot$ 是什么逆天写法 。

可以发现，除了最后一部分，其余部分被划分为了几个长度相同的块

$$\begin{aligned} (n !)_p & =\underbrace{1 \times 2 \times 3 \times \cdots \times(p-2) \times(p-1) \times 1}_{\text {1st}} \times \underbrace{1 \times 2 \times 3 \times \cdots \times(p-2) \times(p-1) \times 2}_{\text {2nd }} \times \cdots \\ & \times \underbrace{1 \times 2 \times 3 \times \cdots \times(p-2) \times(p-1) \times 1}_{p \text { th }} \times \cdots \times \underbrace{1 \times 2 \times \cdots \times (n \bmod p)}_{\text {tail }} \pmod{p} \end{aligned}$$

块的主要部分的 $(p-1)! \bmod{p}$ 很容易计算，可以直接应用威尔逊定理

而最后一个块则可以在 $\mathcal{O}(p)$ 的时间内计算出。

唯一的“难点”在于每个块的最后一位实际上没有被处理（我相信你可能也没注意到）

$$1\times 2 \times \cdots \times (p -1) \times 1\times 1 \times2\times \cdots$$

而这实际上就是

$$\left(\left\lfloor\frac{n}{p}\right\rfloor !\right)_p$$

于是我们预处理 $1$ 到 $p-1$ 的阶乘，即可在单次 $\mathcal{O}(\log_p n)$ 的时间复杂度内回答 $n$ 的答案。

总时间复杂度 $\mathcal{O}(p + q\log_pn)$

代码：（搬的）

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. Legendre 公式

如果想计算二项式系数模 $p$ ，那么还需要考虑在 $n$ 的阶乘的素因子分解中 $p$ 出现的次数

$n!$ 中含有的素数 $p$ 的幂次 $v_p(n!)$ 为

$$v_p(n !)=\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^i}\right\rfloor=\frac{n-S_p(n)}{p-1}$$

其中 $S_p(n)$ 为 $p$ 进制下 $n$ 的各个数位的和。

特别地，阶乘中 $2$ 的幂次是 $v_2(n!) = n - S_2(n)$​ 。

时间复杂度 $\mathcal{O}(\log n)$

代码：

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

3. Kummer 定理

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

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

Kummer 定理：

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

$$v_p\left(\binom{m}{n}\right)=\frac{S_p(n)+S_p(m-n)-S_p(m)}{p-1}$$

特别地，组合数中 $2$ 的幂次是 $v_2\left(\binom{m}{n}\right)=S_2(n)+S_2(m-n)-S_2(m)$​

---

推广

对于素数 $p$ 和正整数 $q$ 有

$$\left(p^{q} !\right)_p \equiv \pm 1\left(\bmod p^q\right)$$

证明：考虑配对一个数与其逆元，也就是考虑关于 $m$ 的同余方程 $m^2\equiv 1 \pmod{p^q}$ 的根的乘积

当 $p^q = 2$ 时仅有唯一的根；当 $p=2$ 且 $q \ge 3$ 时有四根，为 $\pm 1,~(2^{q-1} \pm 1)$ ；否则有两根 $\pm1$​ 。$\square$

因此我们对威尔逊定理中的 $\pm 1$ 有了详细的定义，即

$$\left(p^{q} !\right)_p \equiv \begin{cases}1, & (p=2) \wedge(q \geq 3) \\ -1, & \text { otherwise }\end{cases}$$

下文两个推论中的 $\pm 1$ 均特指这样的定义，即当模数 $p^q$ 取 $2^3$ 及以上 $2$ 的幂时取 $1$ ，其余取 $-1$

推论1

对于素数 $p$ ，正整数 $q$ ，非负整数 $n$ 和 $N_0 = (n \bmod p^q)$ ，有

$$(n !)_p \equiv( \pm 1)^{\left\lfloor n / p^q\right\rfloor}\left(N_{0} !\right)_p \quad\left(\bmod p^q\right)$$

证明：

令 $\prod^{\prime}$ 为不能被 $p$ 整除的数的乘积，则

$$\begin{aligned} (n !)_p & =\prod_{1 \leq r \leq n}{ }^{\prime} r \\ & =\left(\prod_{i=0}^{\left\lfloor n / p^q\right\rfloor-1} \prod_{1 \leq j \leq p^q}{ }^{\prime}\left(i p^q+j\right)\right)\left({\prod_{1 \leq j \leq N_0}}^{\prime}\left(\left\lfloor n / p^q\right\rfloor p^q+j\right)\right) \\[6pt]& \equiv\left(\left(p^{q} !\right)_p\right)^{\left\lfloor n / p^q\right\rfloor}\left(N_{0} !\right)_p \\[6pt]& \equiv( \pm 1)^{\left\lfloor n / p^q\right\rfloor}\left(N_{0} !\right)_p \pmod{p^q} \end{aligned}$$

第二行是将 $1 \times 2 \times 3 \times \cdots \times n$ 记为 $\left(0 \times p^q+1\right) \times\left(0 \times p^q+2\right) \times \cdots \times\left(\left\lfloor n / p^q\right\rfloor p^q+N_0\right)$ 。$\square$

推论2

对于素数 $p$ ，正整数 $q$ 和非负整数 $n$ 有

$$\frac{n !}{p^{\sum_{j \geq 1}\left\lfloor\frac{n}{p^j}\right\rfloor}} \equiv( \pm 1)^{\sum_{j \geq q}\left\lfloor\frac{n}{p^j}\right\rfloor} \prod_{j \geq 0}\left(N_{j} !\right)_p \pmod{p^q}$$

其中 $N_j=\left\lfloor n / p^j\right\rfloor \bmod p^q$​ 。

记 $r = n - m$ 且 $n > m$ ，并记 $\nu(n !)=\sum_{j \geq 1}\left\lfloor n / p^j\right\rfloor$ 有

$$\frac{( \pm 1)^{\sum_{j \geq q}\left(\left\lfloor n / p^j\right\rfloor-\left\lfloor m / p^j\right\rfloor-\left\lfloor r / p^j\right\rfloor\right)}}{p^{\nu(n !)-\nu(m !)-\nu(r !)}}\left(\begin{array}{c} n \\ m \end{array}\right) \equiv \frac{n ! / p^{\nu(n !)}}{\left(m ! / p^{\nu(m !)}\right)\left(r ! / p^{\nu(r !)}\right)} \quad\left(\bmod p^q\right)$$

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

但是这谁记得住啊？！（另：$\nu$ 是 \nu ，不是 $v$ 也不是 $\upsilon$ ，但是这也不重要）

---

参考文献：

[1] https://oiwiki.org/math/number-theory/wilson/