威尔逊定理（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\) 的与上述相同。