浅谈数论 & 组合数学 & 多项式

· · 算法·理论

浅谈数论 & 组合数学 & 多项式

版权声明

本文遵循 CC BY-NC-ND 4.0 协议，作者：@Wyh_dailyAC & @renhongxuuu，转载请获得所有作者的授权。

第一作者：@Wyh_dailyAC；第二作者：@renhongxuuu。对于任何的修改建议请联系第一作者。

前言

本文于 2025 年 7 月由 @renhongxuuu 产出第一版（截至“扩展欧拉定理”一部分）。

后自 2026 年 1 月 26 日起由 @Wyh_dailyAC 对本文格式进行规范，并补充本文的数论内容，同时添加组合数学、多项式内容。

本篇文章为笔记类文章，文章（内容）较为庞大，如有格式上 / 内容上的错误烦请指出、海涵。

注：

本文当前版本（第三版）共 70695 字符，当前版本的阅读时间大约为 74 分钟。

更新日志：

2026 / 2 / 28：修复了一处笔误；增加了单位根反演内容（字符数 67764\rightarrow70695）。

文章结构 - 目录

符号、定义与性质 - 1

数论

说明

数论是一个研究整数的学科。若非特殊说明，本章（数论）所有的未知数均为整数。

引例

先抛出几个引例，供读者思考。

这些题在后面会选讲一部分。

扩展欧几里得算法

明确定义

扩展欧几里得算法（Extended Euclidean algorithm，EXGCD）是一个用来求解形如 ax\equiv b \pmod c 的线性同余方程的整数解的算法。

转化

若想求解形如 ax\equiv b \pmod c 的方程的通解或判断是否有解，不妨根据同余的性质，使原方程等价于 ax+cy=b。

接下来我们求解 x,y 即可（我们不需要考虑 a,c,b \lt 0 时的情况，因为我们可以将方程变为 |a|(\frac{a}{|a|}\times x)+|c|(\frac{c}{|c|}\times y)=b 的形式）。

通解公式

我们先不研究该方程的解，我们研究该方程解的性质： 若 x_1,y_1 是方程 ax+cy=b 的一组解，则 ax_1+cy_1=b，于是：

\begin{aligned} &\Rightarrow ax_1+a\cdot c\cdot k - a\cdot c \cdot k + cy_1=b\\ &\Rightarrow a(x_1+c\times k)+c(y_1-a\times k) =b\\ \end{aligned}

则该方程的所有解为 \begin{cases} x=x_1+c\times k\\ y=y_1-a\times k \end{cases}，接下来只需要求解该方程的一组解即可。

化简

我们不妨令 a^\prime =\frac{a}{\gcd(a,c)},b^\prime =\frac{b}{\gcd(a,c)},c^\prime =\frac{c}{\gcd(a,c)}，则方程 ax+cy=b 可以变形为 a^\prime x+c^\prime y=b^\prime。

显然的，a^\prime,c^\prime \in \mathbb{Z}\ ,\gcd(a^\prime ,c^\prime)=1。

根据 \gcd 的性质，a^\prime x+c^\prime y 可以表示为整数 k \times \gcd(a^\prime ,c^\prime)=k\times 1=k，所以有 a^\prime x+c^\prime y\in \mathbb{Z}。

若 b^\prime \notin \mathbb{Z}，则 a^\prime x+c^\prime y \notin \mathbb{Z}，这与上文矛盾。

所以，方程 ax+cy=b 有解，当且仅当 \gcd(a,c)\mid b。

接下来只需要求解方程 a^\prime x+c^\prime y= b^\prime。

随堂测验：请写出下列方程的通解或说明其无解（注：这里指解为整数解，下同）:

3x\equiv 1 \pmod 9

解：该方程等价于 3x+9y=1，提取 a,b 的最大公约数 3，方程变为 3(x+3y)=1。因为 3 \nmid 1，所以方程 3(x+3y)=1 无解。

变形

方程变为了 ax+by=c（注此时的 a,b 和上面不同，并且 \gcd(a,b)=1）。

我们不妨研究方程 aX+bY=1 中 x,X,y,Y 的关系。

将方程二两边乘以 c，变为 a(X\cdot c)+b(Y\cdot c)=c。

接下来只需要解出方程 aX+bY=1 的满足 \gcd(a,b)=1 的解 X,Y 然后再同时 \times c 即可（即求出 aX+bY=1 的整数解）。

求解

举例
\because aX+bY=1,\gcd(a,b)=1\\ \therefore aX+bY=\gcd(a,b)\\

我们不妨多列几个形如这样的方程,然后令下一层的 a 等于上一层的 b，下一层的 a 等于上一层的 a 取模上一层的 b（这是因为，在通用、形式化的求解过程中，会用到 \gcd(a,b)=\gcd(b,a\bmod b) 这个性质）。

一直列下去，总有一层的 b 会等于 0。求解出最后一层的 X,Y，再寻找现相邻两层 X,Y 的关系即可（注：这里会用下标表示层数）。

举个例子：

\begin{aligned} &133X+403Y=1\\ &\Rightarrow 403X_1+133Y_1 =1\\ &\Rightarrow 133X_2+4Y_2=1\\ &\Rightarrow 4X_3+Y_3=1\\ &\Rightarrow X_3+0\cdot Y_3=1\\ \end{aligned}

解得 X_3=1,Y_3 为任意整数，在此令 Y_3=0。

接下来我们研究 X_n 与 X_{n+1}，Y_n 与 Y_{n+1} 的关系。

我们还是研究 aX+bY=1 这种方程（依旧保证 \gcd(a,b)=1）。

上文提到了，我们可以利用 \gcd(a,b)=\gcd(b,a\bmod b) 这条性质，写出一些隐含递归式的等量关系，以仿照欧几里得算法进行递归 / 迭代求解。

下面给出关键的过程，这其实就是上面例子的延伸：

\begin{aligned} & aX+bY=1,\gcd(a,b)=1\\ &\Rightarrow aX+bY=\gcd(a,b)=1\\ &\gcd(a,b)=\gcd(b,a\bmod b)\\ &\Rightarrow bX_1+(a-b\cdot\lfloor\frac{a}{b}\rfloor)Y_1=1\\ &\Rightarrow aX+bY=bX_1+(a-b\cdot\lfloor\frac{a}{b}\rfloor)Y_1\\ &\Rightarrow aX+bY=aY_1+bX_1-b\cdot\lfloor\frac{a}{b}\rfloor\cdot Y_1\\ &\Rightarrow aX+bY=aY_1+b(X_1-\lfloor\frac{a}{b}\rfloor\cdot Y_1)\\ \end{aligned}

到这很明显了——最终方程的两边是同构的，所以有 X=Y_1,Y=X_1-\lfloor\frac{a}{b}\rfloor\cdot Y_1。

这就是一个很明显的递归关系式！于是我们得到了扩展欧几里得算法的做法。

下面举个例子加深印象：

\begin{aligned} &266x\equiv4 \pmod{806}\\ &\Rightarrow266x+806y=4\\ &\Rightarrow133x+403y=2\\ &\Rightarrow133X+403Y=1\\ &\Rightarrow403Y_{1}+133Y_{1}=1\\ &\Rightarrow133X_{2}+4Y_{2}=1\\ &\Rightarrow4X_{3}+Y_{3}=1\\ &\Rightarrow X_{4}+0\cdot Y_{4}=1\\ &X_{4}\leftarrow1,Y_{4}\leftarrow0\\ &\Rightarrow X_{3}=Y_{4}=0,Y_{3}=X_{4}-Y_{4}\times\lfloor\frac{4}{1}\rfloor=1-0\times 4=1\\ &\Rightarrow X_{2}=1,Y_{2}=-33\\ &\Rightarrow X_{1}=-33,Y_{1}=100\\ &\Rightarrow X=100,Y=-33\\ &\Rightarrow\begin{cases} x=X\times 2=200+403k\\ y=Y\times 2=-66-133k \end{cases} \end{aligned}

小结 & 习题

首先扩展欧几里得的运算过程与欧几里得算法的运算过程基本一致，所以求解 ax\equiv c \pmod b 的时间复杂度也是 O(\log \min(a,b))。

习题：已知一个大于 1000 的数末三位是123，把该数乘了一个正整数x，现在它的末三位为 041，问乘的数 x 最小是多少？

解：根据题意，可以列出方程并求解：

\begin{aligned} &\Rightarrow 123x\equiv41 \pmod {1000}\\ &\Rightarrow 123x+1000y=41\\ &\Rightarrow 123X+1000Y=1\\ &\Rightarrow 1000X_1+123Y_1=1\\ &\Rightarrow 123X_2+16Y_2=1\\ &\Rightarrow 16X_3+11Y_3=1\\ &\Rightarrow 11X_4+5Y_4=1\\ &\Rightarrow 5X_5+Y_5=1\\ &\Rightarrow X_6=1,Y_6=0\\ &\Rightarrow X_5=0,Y_5=1\\ &\Rightarrow X_4=1,Y_4=-2\\ &\Rightarrow X_3=-2,Y_3=3\\ &\Rightarrow X_2=3,Y_2=-23\\ &\Rightarrow X_1=-23,Y_1=187\\ &\Rightarrow X=187,Y=-23\\ &\Rightarrow \begin{cases} x=X\times 41=7667+1000k\\ y=Y\times 41=-943-1000k\\ \end{cases}\\ &\because x \leqslant 1000\\ &\therefore x=(7667+1000k)\bmod1000=667\\ \end{aligned}

习题：已知一个大于 1000 的数末三位是 603，把该数乘了一个正整数 x，现在它的末三位为 201，问乘的数 x 最小是多少？

解：根据题意，可以列出方程并求解：

\begin{aligned} &201x\equiv67 \pmod {1000}\\ &\Rightarrow 201x+1000y=67\\ &\Rightarrow 201X+1000Y=1\\ &\Rightarrow 1000X_1+201Y_1=1\\ &\Rightarrow 201X_2+196Y_2=1\\ &\Rightarrow 196X_3+5Y_3=1\\ &\Rightarrow 5X_4+Y_4=1\\ &\Rightarrow X_5=1,Y_5=0\\ &\Rightarrow X_4=0,Y_4=1\\ &\Rightarrow X_3=1,Y_3=-39\\ &\Rightarrow X_2=-39,Y_2=40\\ &\Rightarrow X_1=40,Y_1=-199\\ &\Rightarrow X=-199,Y=40\\ &\Rightarrow \begin{cases} x=X\times 67=-13333+1000k\\ y=Y\times 67=2680-1000k\\ \end{cases}\\ &\because x \leqslant 1000\\ &\therefore x=(-13333+1000k)\bmod1000=667\\ \end{aligned}

代码实现

long long mod(long long a, long long m) { return (a % m) + m % m; }
void exgcd(long long & x, long long & y, long long a, long long b) {
  if (b == 0) {
    x = 1ll, y = 0ll;
    return;
  }
  exgcd(x, y, b, a % b);
  swap(x, y);
  y -= a / b * x;
}
tuple<pair<long long, long long>, pair<long long, long long>, bool> axbyc(long long a, long long b, long long c) {
  if (a < 0 && b < 0) {
    tuple<pair<long long , long long >, pair<long long , long long >, bool> result = axbyc(-a, -b, -c);
    return result;
  } else if (b < 0) {
    tuple<pair<long long, long long>, pair<long long, long long>, bool> result = axbyc(a, -b, c);
    get<1>(result).first = -get<1>(result).first;
    get<1>(result).second = -get<1>(result).second;
    return result;
  } else if (a < 0) {
    tuple<pair<long long, long long>, pair<long long, long long>, bool> result = axbyc(-a, b, c);
    get<0>(result).first = -get<0>(result).first;
    get<0>(result).second = -get<0>(result).second;
    return result;
  } else {
    ulong long temp = gcd(a, b);
    if (c bmod temp != 0) return {{0, 0}, {0, 0}, 0};
    a /= temp, b /= temp, c /= temp;
    long long x = 0, y = 0;
    exgcd(x, y, a, b);
    x *= c, y *= c;
    return {{x, b}, {y, -a}, 1};
  }
}
pair<long long, bool> SolveCongruenceEquation(long long a, long long b, long long mod) {  // ax ≡ b (mod)
  tuple<pair<long long, long long>, pair<long long, long long>, bool> result = axbyc(a, mod, b);
  if (get<2>(result) == 1) {
    pair<long long, long long> x = get<0>(result);
    return {Mod(x.first, x.second + x.second), 1};
  } else return {0, 0};
}

逆元

明确定义

在我们小学的时候，对实数 a 的倒数的定义是与相乘等于 1 的数。特别的，0 没有倒数。

令 a 的倒数为 b，于是我们就可以用乘 b 来代替除以 a 的操作。

于是我们讨论在模意义下的倒数，也就是逆元。

逆元的定义：满足 ax\equiv1 \pmod c 的整数 x，称为 a 在模 c 意义下的逆元，记为模 c 下的 a^{-1}。

注意：有的时候逆元并不存在。

逆元的作用、意义

习题：已知一个大于 1000 的数末三位是 123，把该数乘了一个正整数 x，现在它的末三位为 041，问乘的数 x 最小是多少？

习题：已知一个大于 1000 的数末三位是 603，把该数乘了一个正整数 x，现在它的末三位为 201，问乘的数 x 最小是多少？

没错，又是这两题。不知道你有没有发现，这两题的答案竟然是一样的。

仔细想想，第一题是要把 123 变为 041，相当于除以三，第二题是要把 603 变为 201，也是除以三，并且都是模 1000 意义下的。

不妨列出方程 3x\equiv1 \pmod {1000}，解得 x=667,于是我们便知道了，除以 3 跟乘 667 在 \bmod1000 的意义下一致。

然后用通解的公式，解出 x 的最小正值即可。

所以，逆元的作用其实就是在模意义下代替倒数，逆元的意义也是如此。

EXGCD 求逆元

根据逆元的定义，显然可以用扩展欧几里得算法求解，这里不再详细叙述这种求法。

求解 a 模 p 的逆元的时间复杂度与扩展欧几里得算法一致，是 O(\log a)。

线性求逆元

如果要求 1 到 n-1 的逆元，如果用扩展欧几里得定理或者其他的算法一个一个算时间复杂度为 O(n \log n)，太慢。

不妨考虑以下算法：

对于 1 到 n-1 的一个数 i，设 r=n \bmod i，将 n 用余数表示法表示为 n=\lfloor \frac{n}{i} \rfloor\times i+r。

于是：

\begin{aligned} &\Rightarrow \lfloor \frac{n}{i} \rfloor \times i + r \equiv 0 \pmod n\\ &\Rightarrow \lfloor \frac{n}{i} \rfloor \times i \times (i^{-1}\times r^{-1}) + r \times (i^{-1}\times r^{-1}) \equiv 0 \pmod n\\ &\Rightarrow \lfloor \frac{n}{i} \rfloor \times r^{-1} +i^{-1} \equiv 0 \pmod n\\ &\Rightarrow i^{-1} \equiv - \lfloor \frac{n}{i} \rfloor \times r^{-1} \pmod n\\ \end{aligned}

又 \because 1^{-1} \equiv 1 \pmod n,\therefore i^{-1} = \begin{cases}1,i=1 \\(-\lfloor \frac{n}{i}\rfloor \times r^{-1}) \bmod n,1<i<n \end{cases}。

由此也得出该算法的时间复杂度为 $O(n)$。 #### 线性求逆元的代码 ```cpp vector<int> inv(n + 1, 1); for (int i = 2; i <= n; i++) inv[i] = mod(-n / i * inv[n % i], n); ``` #### 阶乘求逆元 求 $0$ 到 $n$ 阶乘模 $p$ 的逆元，是可以递推的。 具体公式推导如下： 设 $n!$ 的逆元为 $x$，则有 $n!\cdot x\equiv1\pmod{p}$，推导出来 $(n-1)!\cdot(n\cdot x)\equiv1\pmod{p}$。 这里两式同构，所以 $n\cdot x$ 就是 $(n-1)!$ 的逆元。 形式化地，把 $n!$ 的逆元表示为 $invf_{n}$，则有 $invf_{n-1}=(invf_{n}\cdot n)\bmod p$。 所以只需要先求出 $n$ 的逆元，再从 $n$ 到 $1$ 遍历求逆元即可，时间复杂度为 $O(n)$。 #### 阶乘求逆元的代码 ```cpp for (int i = n; i >= 1; i--) inv[i - 1] = (inv[i] * i) % p; ``` 上面代码假定 $invf_{n}$ 已使用 EXGCD / 其他算法求出。 --- ### 中国剩余定理（孙子定理） #### 定义 对于形如$\begin{cases}x\equiv a_1\pmod {m_1}\\x\equiv a_2 \pmod {m_2}\\\dots\\x\equiv{a_n}\pmod {m_n}\end{cases}$的方程组，称为**线性同余方程组**，而**中国剩余定理**（***Chinese Remainder Theorem***）算法可以求解。 具体的，当 $m_1\dots m_n$ 两两互质时，该方程组适用中国剩余定理以求解。 #### 核心思想 令 $M=\Pi _{i=1} ^{n} m_i,M_i=\frac{M}{m_i}$。 我们发现，当 $j\neq i$ 时，$kM_i\equiv 0 \pmod {m_j}$，接下来令 $kM_i\equiv a_i \pmod {m_i}$，就有 $kM_i$ 对于第 $i$ 条线性同余方程是正确的，并且对于除第 $i$ 条外的方程不影响。我们不妨将 $1$ 至 $n$ 的所有 $kM_i$ 求解并求和，就可以得到一个解，再将其取模 $M$，就是答案的最小正值。 举例： $$ \begin{aligned} &\left\{\begin{matrix} x \equiv 2 \pmod 3\\ x \equiv 3 \pmod 5\\ x \equiv 2 \pmod 7\\ \end{matrix}\right.\\ &\Rightarrow 35k\equiv2 \pmod 3\Rightarrow k=1\\ &\Rightarrow 21k\equiv3 \pmod 5\Rightarrow k=3\\ &\Rightarrow 15k\equiv2 \pmod 7\Rightarrow k=2\\ &\Rightarrow x_1=35\times 1+21 \times 3 + 15 \times 2=128\\ &\Rightarrow x=128 \bmod (3\times 5 \times 7)=23 \end{aligned} $$ 因为 $m$ 两两互质，所以不用担心 $kM_i\equiv a_i \pmod {m_i}$ 这些方程无解 #### 习题 > 习题：是否存在 $21$ 个连续的正整数，使得其中每个数均被至少一个 $2 \sim 13$ 的素数整除？若有，请写出这 $21$ 个正整数的中间数的最小值；若没有，请说明理由（此题留给读者自行解答）。 #### 代码实现 `````cpp pair<long long, bool> SolveCongruenceEquation(long long a, long long b, long long mod); // 求解ax ≡ b (mod) long long ChineseRemainderTheorem(vector<long long>& rmdi, vector<long long>& modi) { long long factor = 1, result = 0; for (long long x : modi) factor *= x; for (int i = 0; i < rmdi.size(); i++) result += factor / modi[i] * SolveCongruenceEquation(factor / modi[i], rmdi[i], modi[i]).first; return result bmod factor; } ````` #### 扩展中国剩余定理 其实就是把线性同余方程转化为不定方程，然后使用扩展欧几里得算法求解 / 得到无解。 具体地，先讨论两个方程组成的线性同余方程组 $\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\end{cases}$。 可以将两个方程组转化并拼接为 $x=m_{1}k_{1}+a_{1}=m_{2}k_{2}+a_{2}$。 考虑求出 $k_1,k_2$ 以进一步求出 $x$，即求出 $m_1k_1-m_2k_2=a_2-a_1$ 这个不定方程的特解。 设若求出一组特解 $(k_1,k_2)$，然后凑出一个方程 $x\equiv m_1k_1+a_1\pmod{\operatorname{lcm}(m_1,m_2)}$，这个同余方程的解就是 $\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\end{cases}$ 这个线性同余方程的解。 对于多个方程的情况，把方程按上面做法两两合并，直至只有一个方程即可。 在此不再说明此算法的正确性，易证。 ### 欧拉函数及定理 #### 定义 $\varphi(x)$：欧拉函数，即 $1\sim x$ 中**与 $x$ 互质的数的个数**。 特别的，$\varphi (1)=1$。 #### 性质 - $\varphi(1)=1$。 - $\varphi(p)=p-1$（$p$ 为质数）。 - $\varphi(p^b)=p^b-p^{b-1}$（$p$ 为质数）。 - 欧拉函数是**积性函数**，即若 $\gcd(a,b)=1,\varphi(a\times b)=\varphi(a)\times \varphi(b)$。 - $\varphi(x)=x\times \Pi _{i=1} ^n (1-\frac{1}{p_i})$（$n$ 为 $x$ 分解质因数后的质数个数）。 - 欧拉定理：若 $\gcd(a,x)=1$，则 $a^{\varphi(x)}\equiv 1 \pmod x$。 #### 性质的证明 ##### $\varphi(p^b)=p^b-p^{b-1}$ 的证明 回归定义，$\varphi(p^b)$ 是 $1\sim p^b$ 中与 $p^b$ 互质的数的个数。 记 $1\sim p^b$ 中与 $p^b$ 不互质的数的个数为 $t$，即 $\varphi(p^b)=p^b-t$。 那么 $1\sim p^b$ 中与 $p^b$ 不互质的数到底有多少呢？ 因为 $p$ 为质数，所以不互质 $p^b$ 的数一定是 $p$ 的倍数：$1p,2p,3p,\cdots p^{b-1}\times p$，一共有 $p^{b-1}$ 个。 所以 $\varphi(p^b)=p^b-p^{b-1}$。证毕。 --- ##### $\gcd(a,b)=1\Rightarrow\varphi(a\times b)=\varphi(a)\times \varphi(b)$ 的证明 还是刚才的那个思想，$\varphi(a\times b)=1$ 到 $ab$ 中与 $ab$ 互质的数的个数。 我们列出 $1 \sim ab$ 的所有整数： | 原数 | 原数模$a$的结果 | 原数模$b$的结果 | | ---- | --------------- | --------------- | | $1$ | $1 \bmod a$ | $1 \bmod b$ | | $2$ | $2 \bmod a$ | $2 \bmod b$ | | ⋮ | ⋮ | ⋮ | | $ab$ | $0$ | $0$ | 将右两列组成数对 $(x \bmod a, x \bmod b)$。 因为 $\gcd(a,b)=1$，有： $$\gcd(x, ab) = 1 \iff \gcd(x, a) = 1 \ \\ \gcd(x, b) = 1 \iff \gcd(x \bmod a, a) = 1\ \\ \gcd(x \bmod b, b) = 1$$ **所以，当且仅当$x$同时满足以下两个条件时，$x$ 与 $ab$ 互质：** $\begin{cases} \gcd(x \bmod a, a) = 1 \\ \gcd(x \bmod b, b) = 1 \end{cases}

因为 a 和 b 互质，所有数对 (x \bmod a, x \bmod b) 互不相同（即不同 x 对应不同数对），因此原数 x 与数对 (u,v) 一一对应。

观察数对中的分量：

要同时满足两个互质条件，数对的选择数量为：

\varphi(a \times b) = \varphi(a) \times \varphi(b)

举例： a=3,b=5，则 ab=15 。

原数 模3余数 模5余数 与15互质条件
1 1 1 是
2 2 2 是
3 0 3 否
4 1 4 是
5 2 0 否
6 0 1 否
7 1 2 是
8 2 3 是
9 0 4 否
10 1 0 否
11 2 1 是
12 0 2 否
13 1 3 是
14 2 4 是
15 0 0 否

表中加粗表示满足与该模数互质：

同时满足两个条件的数有 8 个，即 \varphi(15)=8=\varphi(3)\times\varphi(5)。

\varphi(x)=x\times \Pi _{i=1} ^n (1-\frac{1}{p_i}) 的证明

想要求 x 的值，不妨将它质因数分解。假设 x=\Pi _{i=1}^n p_i^{a_i}，则 \varphi(x)=\varphi(\Pi _{i=1}^n p_i^{a_i})。

又 $\because p_i$ 为质数，所以： $$\varphi(x)=\Pi _{i=1} ^n (p_i^{a_i}-p_i^{a_i-1})=\Pi _{i=1} ^n p_i^{a_i}(1-\frac{1}{p_i})=\Pi _{i=1} ^n p_i^{a_i} \times \Pi_{i=1}^n (1-\frac{1}{p_i})=x \Pi_{i=1} ^n (1-\frac{1}{p_i})$$ 证毕。 ##### 欧拉定理的证明 假设 $a$ 与 $x$ 互质，且 $0 \leqslant a < x$。考虑 $1$ 至 $x$ 中与 $x$ 互质的所有整数，记为 $b_1,b_2,\dots,b_{\varphi(x)}$。定义 $c_i = b_i \times a$ 和 $d_i = c_i \bmod x$。 序列 $b$ 满足：当 $i \neq j$ 时，$\ b_i \neq b_j$；$\gcd(b_i, x) = 1$。 分析 $d_i$ 的性质：问题：$d_i = d_j$ 是否可能成立（对于 $i \neq j$）？ 反证法：假设 $d_i = d_j$（其中 $i \neq j$），则 $c_i \equiv c_j \pmod{x}$，即 $(b_i \times a \equiv b_j \times a \pmod{x})$。 由同余性质，得 $a(b_i - b_j) \equiv 0 \pmod{x}$。 由于 $\gcd(a, x) = 1$，因此 $b_i - b_j \equiv 0 \pmod{x}$。 又因为 $1 \leqslant b_i,b_j \leqslant x$，故 $b_i = b_j$，与条件 $i \neq j$ 矛盾。 因此，$d_i \neq d_j$，即 $d$ 满足互异性。 互质性：$\gcd(d_i, x) = \gcd(c_i \bmod x, x) = \gcd(c_i, x) = \gcd(a \times b_i, x)$。 由于 $\gcd(a, x) = 1$ 且 $\gcd(b_i, x) = 1$，有 $\gcd(a \times b_i, x) = 1$。 因此，$\gcd(d_i, x) = 1$，即 $d$ 满足互质性。 综上，序列 $d$ 与 $b$ 除了顺序可能不同，其他均相同。 欧拉定理的推导：由于 d 是 b 的重新排列，其乘积满足 $b_1 b_2 \cdots b_{\varphi(x)} \equiv d_1 d_2 \cdots d_{\varphi(x)} \pmod{x}$。 又因为 $d_i \equiv a b_i \pmod{x}$，故 $d_1 d_2 \cdots d_{\varphi(x)} \equiv (a b_1)(a b_2)\cdots[a b_{\varphi(x)}] \pmod{x}$。 因此，$b_1 b_2 \cdots b_{\varphi(x)} \equiv a^{\varphi(x)} [b_1 b_2 \cdots b_{\varphi(x)}] \pmod{x}$。 整理得 $[a^{\varphi(x)} - 1] b_1 b_2 \cdots b_{\varphi(x)} \equiv 0 \pmod{x}

由于每个 b_i 与 x 互质，其乘积 b_1 b_2 \cdots b_{\varphi(x)} 也与 x 互质（因数均互质）。

故 a^{\varphi(x)} - 1 \equiv 0 \pmod{x}，所以 a^{\varphi(x)} \equiv 1 \pmod{x}。证毕。

欧拉定理

当 \gcd(a,n)=1 时，a^b\equiv a^{b \bmod \varphi(n)} \pmod n。

证明:

设 r=b \bmod \varphi(n),k=\frac{b-r}{\varphi(n)}。

\Rightarrow a^b \equiv a^{k\varphi(x)+r}\equiv [a^{\varphi(x)}]^{k}\times a^r \equiv 1^k \times a^r \equiv a^r \equiv a ^{b \bmod \varphi(n)} \pmod n\\

习题

欧拉定理求逆元，费马小定理，扩展欧拉定理

欧拉定理求逆元

根据欧拉定理，当 \gcd(a,n) 时，a^{\varphi(n)}\equiv 1 \pmod n，

$\therefore a^{\varphi(n)-1}+k\times n$ 是 $a$ 模 $n$ 的逆元。 #### 费马小定理 **当 $n$ 为质数且 $n \nmid a$ 时，$a^{n-1}\equiv 1 \pmod n$。** 证明（有多种证明方法，这里给出一种最简单的）: 因为 $n\nmid a$ 且 $n$ 是质数，所以 $\gcd(a,n)=1$。 根据欧拉定理，$\therefore a^{\varphi(n)}\equiv 1 \pmod n$。 又因为 $n$ 为质数，所以 $\varphi(n)=n-1$，所以 $a^{n-1}\equiv 1 \pmod n$。证毕。 #### 费马小定理求逆元 根据费马小定理，当 $n$ 为质数时，有 $a^{n-1} \equiv 1 \pmod n$， $\therefore a\times a^{n-2} \equiv 1 \pmod n$， $\therefore (a^{n-2}+kn)$ 是 $a$ 模 $n$ 的逆元（最小化正整数逆元即 $a^{n-2}$）。 #### 扩展欧拉定理 ##### 定理 对于任意的 $a,b,c \in \mathbb{N^+}$，满足 $a^b \equiv \begin{cases} a^b & b \lt \varphi(c)\\ a^{(b\bmod \varphi(c))+\varphi(c)} & b \geqslant \varphi(c) \end{cases} \pmod c$。 其中第一行表示 $a^b \bmod c$ 在 $b \lt \varphi(c)$ 时无法用欧拉定理降幂。 ##### 定理的证明 接下来我们证明第二行 $a^b \equiv a^{(b \bmod \varphi(c)) +\varphi(c)} \pmod c$。 - 先证明两个引理： - 引理一：如果 $p,q$ 互质，且有 $x\equiv y \pmod p ,x\equiv y \pmod q$，那么有 $x\equiv y \pmod {pq}$。 根据同余的性质，有 $x-y = k_1 p,x-y = k_2 q$，其中 $k_1,k_2\in\mathbb{Z}$。 于是有如下过程： $$ \begin{aligned} &\because p\mid x-y,q\mid x-y\\ &\therefore \operatorname{lcm}(p,q) \mid (x-y)\\ &\because \gcd(p,q)=1\\ &\therefore pq\mid x-y\\ &\therefore x\equiv y \pmod {pq} \end{aligned} $$ - 引理二：对于素数的整数次幂 $p^e$，有 $\varphi(p^e)\geqslant e$。 证：只需证明极端情况“$p$ 最小”时成立即可，即证 $2^{e-1}\geqslant e$。 注意到，当 $e=1$ 时显然成立。 假设不等式在 $k$ 处成立，需证它在 $k+1$ 处也成立（$k\ge1$）。 于是有如下过程： $$ \begin{aligned} &\because 2^{k-1} \geqslant k\\ &\therefore 2^k \geqslant 2k\\ &\because k \geqslant 1\\ &\therefore 2k \geqslant k+1\\ &\therefore 2^k \geqslant 2k \geqslant k+1\\ \end{aligned} $$ - 将 $c$ 质因数分解，设 $c=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$。 根据同余性质，若 $p,q$ 互质，且 $x\equiv y \pmod p$,$x\equiv y \pmod q$，那么 $x\equiv y \pmod {pq}$。 根据引理一，只需证明对于每个 $p_i^{e_i}$，满足 $a^b \equiv a^{(b\bmod \varphi(c))+\varphi(c)} \pmod {p_i^{e_i}}$。 - $\gcd(a,p_i^{e_i})=1$ 时 根据欧拉定理有 $a^{\varphi(p_i^{e_i})}\equiv 1 \pmod {p_i^{e_i}}$。 由欧拉函数的积性可得 $a^{\varphi(c)}\equiv a^{\varphi(p_i^{e_i})\times k} \equiv 1 \pmod {p_i^{e_i}}$。 根据余数表示法有 $b=\lfloor \frac{b}{\varphi(c)} \rfloor \times \varphi(c) + b \bmod \varphi(c)$。 $\therefore a^b \equiv a^{\lfloor \frac{b}{\varphi(c)} \rfloor \times \varphi(c) + b\bmod \varphi(c)} \equiv a^{\lfloor \frac{b}{\varphi(c)} \rfloor \varphi(c)} \times a^{b\bmod \varphi(c)}\equiv 1\times a^{b \bmod \varphi(c)}\equiv a^{b \bmod \varphi(c)}\times a^{\varphi(c)}\equiv a^{(b \bmod \varphi(c)) +\varphi(c)} \pmod {p_i^{e_i}}$。 - $\gcd(a,p_i^{e_i}) \neq 1$ 时 因为 $p_i$ 为质数且 $\gcd(a,p_i^{e_i}) \neq 1$，所以 $p_i \mid a$。 设 $a=np_i$。 因为 $b\geqslant \varphi(c),\varphi(p_i^{e_i})\geqslant e_i$ 且欧拉函数是积性函数，所以有不等式 $b \geqslant \varphi(c) \geqslant \varphi(p_i^{e_i}) \geqslant e_i$。 $\because a=np_i\\ \therefore a^b = {(np_i)}^b = n^b \times p_i^{b-e_i}\times p_i^{e_i}\\ \because b\geqslant e_i\\ \therefore p_i^{e_i} \mid a^b,a^b \equiv 0 \pmod {p_i^{e_i}}\\ 
同理可得 $a^{(b\bmod \varphi(c))+\varphi(c)}={(np_i)}^{(b\bmod \varphi(c))+\varphi(c)}=n^{(b\bmod \varphi(c))+\varphi(c)}\times p_i^{(b\bmod \varphi(c))+\varphi(c)-e_i}\times p_i^{e_i} \pmod {p_i^{e_i}}$。

$\\
\therefore p_i^{e_i} \mid a^{(b\bmod \varphi(c)) +\varphi(c)},a^{(b \bmod \varphi(c))+\varphi(c)}\equiv 0 \pmod {p_i^{e_i}}\\
\therefore a^b \equiv a^{(b\bmod \varphi(c))+\varphi(c)} \pmod {p_i^{e_i}}$

证毕。

意义

我们在使用欧拉定理降幂时，不需要考虑 a,c 互不互质了。

在我们只会欧拉定理时，当 a,c 不互质时，使用的方法是拆模数；现在会了扩展欧拉定理，就多了一种方法，但不代表前一种方法没用了，因为扩展欧拉定理降幂的模数很难达到最优。

再谈线性同余方程 & 高次同余方程

在“中国剩余定理”一章中，我们初步谈及了线性同余方程（组）。

现在让我们继续深入地探讨更普适的同余方程定义、性质，而不局限于线性同余方程。

这部分的内容将会为后面的原根、阶乘取模的讲解做铺垫。

同余方程重定义

考虑普通的 n 次多项式可以如何表示。

对于一个 n 次多项式，获取其所有项系数 a_0\dots a_{n} 后，可以将其表示为 \sum_{i=0}^{n}a_{i}x^{i}。

那么现在给出 n 次同余方程的定义：对正整数 m 和一元整系数多项式 f'(x)=\sum_{i=0}^{n}a_{i}x^{i}，不妨一般化同余式，令 f(x)\leftarrow f'(x)-f'(x)\bmod m，则有 f(x)\equiv0\pmod{m}，这式子就是一元同余方程；如果满足 a_{i}\not\equiv0\pmod{m}，那么这个方程就是 n 次（一元）同余方程。

注意，在模 m 意义下的同余方程中，x\in\mathbb{Z_{p}}（即 x 属于模 m 剩余类环）。

模素数多项式因式分解定理

特别形式化的说法已经不是人话了，这里给定一个能看懂的说法。

定理内容

设 n 次一元同余方程 f(x)\equiv0\pmod{m}，如果此方程有 k 个互不同余的根 x_1\dots x_{k}，则定有唯一的 n-k 次多项式 g(x)，满足 g(x) 最高次项系数为 a_{n} 且 f(x)\equiv g(x)\prod_{i=1}^{k}(x-x_{i})\pmod{m}。

注意 m\in\mathbb{P} 时本定理才成立（即 m 属于素数时本定理成立，否则非也）。

证明

下面 \deg 表示次数；\mathbb{F}_p[x] 表示模 p 剩余类域上的多项式环；\mathbb{F}_p 与 \mathbb{Z}_p 混淆使用（前者绝对表示模 p 剩余类域）。

先使用带余除法进行转化：

对任意 f(x), h(x) \in \mathbb{F}_p[x] 且 h \neq 0，存在唯一的 q(x), r(x) \in \mathbb{F}_p[x] 使得

f(x) = q(x)h(x) + r(x)

其中 \deg r < \deg h 或 r = 0。

引理：设 F 是域，f(x) \in F[x]，c \in F。则 f(c) = 0 当且仅当 (x - c) \mid f(x)（在 F[x] 中）。

证明引理：

我们对根的个数 k 进行归纳证明。

基例 k = 0： 若 f(x) \equiv 0 \pmod{p} 无解，直接取 g(x) = f(x)，空乘积定义为 1，定理显然成立。

归纳假设： 假设定理对所有在 \mathbb{F}_p 中拥有 k-1 个不同根的多项式成立。

归纳步骤（从 k-1 到 k）： 设 f(x) 有 k 个不同根 x_1, \dots, x_k。

  1. 提取第一个根：

    由引理，因为 f(x_1) = 0，存在 f_1(x) \in \mathbb{F}_p[x] 使得：

    f(x) = (x - x_1) \cdot f_1(x)

    次数关系：\deg f_1 = \deg f - 1 = n - 1。

  2. 分析剩余根：

    对 i = 2, \dots, k，代入 x = x_i：

    0 = f(x_i) = (x_i - x_1) \cdot f_1(x_i)

    因为 x_i \not\equiv x_1 \pmod{p}（根互不相同），且 \mathbb{F}_p 是域（无零因子），必有：

    f_1(x_i) = 0 \quad \text{对 } i = 2, \dots, k

    因此 f_1(x) 有根 x_2, \dots, x_k，共 k-1 个不同根。

  3. 应用归纳假设：

    由归纳假设，存在 g(x) \in \mathbb{F}_p[x] 使得：

    f_1(x) = g(x) \cdot \prod_{i=2}^k (x - x_i)

    且 \deg g = (n-1) - (k-1) = n - k。

  4. 合并：

    f(x) = (x - x_1) \cdot f_1(x) = g(x) \cdot \prod_{i=1}^k (x - x_i)\\ f(x)\equiv g(x)\prod_{i=1}^{k}(x-x_{i})\pmod{m}

设 f(x) 的首项为 a_n x^n，g(x) 的首项为 b x^{n-k}（因为 \deg g = n-k）。

乘积 \prod_{i=1}^k (x - x_i) 的首项为 x^k（首一多项式）。

因此：

f(x) = g(x) \cdot \prod_{i=1}^k (x - x_i)

右边首项为 b \cdot x^{n-k} \cdot x^k = b x^n。

与左边 a_n x^n 比较得 b = a_n。

即 [x^{n-k}]g(x) = a_n。

唯一性：满足条件的 g(x) 是唯一的。

证明：假设存在 g_1(x), g_2(x) 都满足条件，则：

g_1(x) \cdot \prod_{i=1}^k (x - x_i) \equiv g_2(x) \cdot \prod_{i=1}^k (x - x_i) \pmod{p}

因为 \mathbb{F}_p[x] 是整环（无零因子），且 \prod (x - x_i) \not\equiv 0，可两边约去，得 g_1(x) \equiv g_2(x)。

推论：拉格朗日定理（Lagrange theorem）

设 n 次一元同余方程 f(x)\equiv0\pmod{m}，其中 m\in\mathbb{P}，则此方程至多有 n 个根。

证明：反证。假设上方程有 n+1 个互不同余的根 x_1\dots x_{n+1}，则由“模素数多项式因式分解定理”对 x_1\dots x_n 有：

f(x)\equiv g(x)\prod_{i=1}^{n}(x-x_{i})\pmod{m}

由于 g(x) 最高次项的未知数系数为 n-k，而此处 k=n，所以 n-k=0，所以 g(x) 退化为了常数 a_{n}。

带入 x=x_{n+1},g(x)=a_{n} 有：

0\equiv f(x_{n+1})\equiv a_{n}\prod_{i=1}^{n}(x_{n+1}-x_{i})\pmod{m}

而 a_n\not\equiv0\pmod{m},x_{n+1}\not\equiv0\pmod{m}，则 a_{n}\prod_{i=1}^{n}(x_{n+1}-x_{i}) 中任何一个因子都不与 m 在模 m 意义下同余，所以它们的乘积模 m 值必然不为 0。假设与方程矛盾，故假设不成立，此方程不可能有 \ge n+1 个互不同余根。故“此方程至多有 n 个互不同余的根”成立。证毕。

高次同余方程的解法

对于高次剩余，有一些较为适用的算法求解，下文中的内容里会讲到。

阶

定义

给定整数 a 与正整数 n，且 \gcd(a,n)=1。a 在模 n 意义下的阶，即满足 a^k\equiv 1\pmod{n} 的最小正整数 k，记作 \delta_{n}(a)。

对于一个正整数 n，所有 a\perp n 的阶 \delta_n(a) 的最小公倍数，记作 \lambda(n)。

阶的意义

在模运算中，大指数的情况常常出现。过去我们尝试过通过扩展欧拉定理等方法降幂，但我们从来没有考虑过幂运算在模意义下的规律，从而错失了很大一块的降幂优化空间。

而阶，就是采用了对指数进行带余除法，来得到形如 (a^{\delta_{n}(a)})^q 的整块的、与 1 同余的式子以省略乘式的方法，从而降幂、减少计算量。

同时，阶还是离散对数、指数 DP 的理论基础。

总而言之，数论中不能失去阶，阶是数论中一个重要的板块。

阶的性质

注：如无特殊说明，“阶的性质”一部分的代数式以及条件均与“定义”一部分保持一致。

阶的存在性

由欧拉定理知当 \gcd(a,n)=1 时，a^{\varphi(n)}\equiv1\pmod{n}。

又根据欧拉函数定义，可得 \varphi(n)>0，所以可得阶一定存在。

阶的唯一性

由阶为“条件集合中最小的数值”这条定义易得。

对 \delta_{n}(a)\mid\varphi(n) 的证明

证：由“阶的存在性”的证明可得 \delta_{n}(a)\le\varphi(n)，不妨将 \varphi(n) 表示成 q\delta_{n}(a)+r 的形式，则依据欧拉定理有 a^{q\delta_{n}(a)+r}\equiv1\pmod{n}。

那么化简，得 (a^{\delta_{n}(a)})^q\cdot a^r\equiv1\pmod{n}，又因为 a^{\delta_{n}(a)}\equiv1\pmod{n}，所以原式可化简为 a^r\equiv1\pmod{n}。

根据阶最小性质，可得此时必须取 r=0 才能取到满足 a^k\equiv 1\pmod{n} 的最小正整数 k（即 \delta_{n}(a)）。

所以 \varphi(n)=q\delta_{n}(a)，于是证得 \delta_{n}(a)\mid\varphi(n)。证毕。

由此推广，对于满足 a^k\equiv 1\pmod{n} 的任意正整数 k，都有 \delta_{n}(a)\mid k。

证明 \delta_{n}(a^k)=\frac{\delta_{n}(a)}{\gcd(\delta_{n}(a),k)}

证：由“满足 a^k\equiv 1\pmod{n} 的任意正整数 k，都有 \delta_{n}(a)\mid k”可得 \frac{\delta_{n}(a)}{\gcd(\delta_{n}(a),k)}\mid n，而 n 最小为 \delta_{n}(a^k)，所以有 \delta_{n}(a^k)=\frac{\delta_{n}(a)}{\gcd(\delta_{n}(a),k)}。证毕。

接下来是关于乘积的阶的一些性质与其证明，讲解会很详细，但读者要有一定的群论基础。

命题 1：佚名

定理：设 a,b\in\mathbb{Z}，m\in\mathbb{N}^+，且 (a,m)=(b,m)=1。则必存在 c\in\mathbb{Z} 且 (c,m)=1，使得

\delta_m(c)=\big[\delta_m(a),\delta_m(b)\big].

证：我们将分三步完成证明：先化归到素数幂模数的情形；再对素数幂分别处理（奇素数与 p=2 区别对待）；最后由中国剩余定理（CRT）拼接。

步骤 1：化归到 m=p^k

设 m 的标准分解为 m=\prod_{i=1}^r p_i^{k_i}。由中国剩余定理，有群同构

(\mathbb{Z}/m\mathbb{Z})^\times \cong \prod_{i=1}^r (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times.

对任意 x 与 m 互素，记 \delta_{p_i^{k_i}}(x) 为 x 模 p_i^{k_i} 的阶，则显然有

\delta_m(x)=\big[\delta_{p_1^{k_1}}(x),\delta_{p_2^{k_2}}(x),\dots,\delta_{p_r^{k_r}}(x)\big].

因此，若对每个 i 都能找到 c_i 使得 \delta_{p_i^{k_i}}(c_i)=\big[\delta_{p_i^{k_i}}(a),\delta_{p_i^{k_i}}(b)\big]，再取 c 满足同余方程组 c\equiv c_i\pmod{p_i^{k_i}}\ (i=1,\dots,r)，则必有

\delta_m(c)=\big[\big[\delta_{p_i^{k_i}}(a)\big],\big[\delta_{p_i^{k_i}}(b)\big]\big]=\big[\delta_m(a),\delta_m(b)\big].

故只需对 m=p^k（素数幂）证明结论。

步骤 2：m=p^k 的情形

(i) p 为奇素数，或 p=2 且 k\le 2。

此时乘法群 (\mathbb{Z}/p^k\mathbb{Z})^\times 是循环群。设其生成元为 g，阶为 \varphi(p^k)。则存在整数 \alpha,\beta 使得

a\equiv g^\alpha\pmod{p^k},\qquad b\equiv g^\beta\pmod{p^k}.

由循环群中元素阶的公式，有

\delta_{p^k}(a)=\frac{\varphi(p^k)}{(\varphi(p^k),\alpha)},\qquad \delta_{p^k}(b)=\frac{\varphi(p^k)}{(\varphi(p^k),\beta)}.

记 n=\varphi(p^k)，d=\delta_{p^k}(a)，e=\delta_{p^k}(b)。我们要找 c\equiv g^\gamma\pmod{p^k} 使得 \delta_{p^k}(c)=[d,e]。计算得

[d,e]=\left[\frac{n}{(n,\alpha)},\frac{n}{(n,\beta)}\right]=\frac{n}{\big((n,\alpha),(n,\beta)\big)}=\frac{n}{(n,\alpha,\beta)}.

于是只需取 \gamma 满足 (n,\gamma)=(n,\alpha,\beta)。显然取 \gamma=(n,\alpha,\beta) 即可（因为此时 (n,\gamma)=\gamma=(n,\alpha,\beta)）。于是令

c\equiv g^{(n,\alpha,\beta)}\pmod{p^k},

则有 \delta_{p^k}(c)=[d,e]，得证。

(ii) p=2 且 k\ge 3。

此时 (\mathbb{Z}/2^k\mathbb{Z})^\times\cong C_2\times C_{2^{k-2}}，其中 C_2=\{\pm 1\} 由 -1 生成，C_{2^{k-2}} 由 5 生成。于是可设

a\equiv (-1)^{u_1}5^{v_1}\pmod{2^k},\qquad b\equiv (-1)^{u_2}5^{v_2}\pmod{2^k},

其中 u_1,u_2\in\{0,1\}，v_1,v_2\in\mathbb{Z}。

记 d_1=\delta_{2^{k-2}}(5^{v_1})=\frac{2^{k-2}}{(2^{k-2},v_1)}，d_2=\delta_{2^{k-2}}(5^{v_2})=\frac{2^{k-2}}{(2^{k-2},v_2)}。则

\delta_{2^k}(a)=2^{u_1}\cdot d_1,\qquad \delta_{2^k}(b)=2^{u_2}\cdot d_2.

我们需要构造 c\equiv (-1)^w 5^z\pmod{2^k} 使得 \delta_{2^k}(c)=[2^{u_1}d_1,2^{u_2}d_2]。

取 w=\max\{u_1,u_2\}，则 2^w=[2^{u_1},2^{u_2}]。
对循环群 \langle 5\rangle 应用 (i) 的结论，存在 z 使得 \delta_{2^{k-2}}(5^z)=[d_1,d_2]。

于是令 c\equiv (-1)^w 5^z\pmod{2^k}，则有

\delta_{2^k}(c)=2^w\cdot[d_1,d_2]=[2^{u_1}d_1,2^{u_2}d_2]=[\delta_{2^k}(a),\delta_{2^k}(b)].
步骤 3：拼接

对每个 i=1,\dots,r，已得 c_i 满足 \delta_{p_i^{k_i}}(c_i)=[\delta_{p_i^{k_i}}(a),\delta_{p_i^{k_i}}(b)]。由 CRT 取 c 满足 c\equiv c_i\pmod{p_i^{k_i}}，则

\delta_m(c)=\big[[\delta_{p_i^{k_i}}(a)],[\delta_{p_i^{k_i}}(b)]\big]=[\delta_m(a),\delta_m(b)].

证毕。

命题 2：乘积阶的夹逼定理

定理：设 a,b\in\mathbb{Z}，m\in\mathbb{N}^+，且 (a,m)=(b,m)=1。记

d=\delta_m(a),\quad e=\delta_m(b),\quad g=(d,e),\quad l=[d,e].

则有

\frac{l}{g}\;\mid\;\delta_m(ab)\;\mid\;l.

证：记 f=\delta_m(ab)。我们分别证明右半部分与左半部分。

右半部分：f\mid l

因为 l=[d,e]，故 d\mid l 且 e\mid l。于是

(ab)^l=a^l\cdot b^l=(a^d)^{l/d}\cdot(b^e)^{l/e}\equiv 1^{l/d}\cdot 1^{l/e}\equiv 1\pmod m.

根据阶的定义（最小性），必有 f\mid l。

左半部分：\frac{l}{g}\mid f

由 (ab)^f\equiv 1\pmod m 可得 a^f\equiv b^{-f}\pmod m。

设 x\equiv a^f\equiv b^{-f}\pmod m。对 a^f 而言，其阶为 \delta_m(a^f)=\frac{d}{(d,f)}（这是因为 (a^f)^k\equiv 1\Leftrightarrow d\mid fk\Leftrightarrow \frac{d}{(d,f)}\mid k）。同理，b^{-f} 的阶为 \delta_m(b^{-f})=\delta_m(b^f)=\frac{e}{(e,f)}。

因为 a^f\equiv b^{-f}，二者相等，故其阶必等：

\frac{d}{(d,f)}=\frac{e}{(e,f)}.

交叉相乘得

d\cdot(e,f)=e\cdot(d,f).

两边同除以 g=(d,e)，得

\frac{d}{g}\cdot(e,f)=\frac{e}{g}\cdot(d,f).

注意到 \big(\frac{d}{g},\frac{e}{g}\big)=1。由上式，\frac{d}{g} 整除右边 \frac{e}{g}\cdot(d,f)，但与 \frac{e}{g} 互素，故必有

\frac{d}{g}\mid(d,f).

于是 \frac{d}{g}\mid f。同理可得 \frac{e}{g}\mid f。

因为 \frac{d}{g} 与 \frac{e}{g} 互素，且同整除 f，故其乘积亦整除 f：

\frac{d}{g}\cdot\frac{e}{g}\;\big|\;f.

而 \frac{d}{g}\cdot\frac{e}{g}=\frac{de}{g^2}=\frac{[d,e]}{g}=\frac{l}{g}。

综上，得到 \frac{l}{g}\mid f\mid l。证毕。

原根

终于讲到原根了——NOI 八级考点。

让我们先形式化地定义一下原根。

定义

给定整数 g 与正整数 n，且 \gcd(g,n)=1。如果 \delta_{n}(g)=\varphi(n)，那么 g 就是一个模 n 下的原根。

含义

原根的含义，其实从汉语的书写中去理解会更好一些。

“原”“根”，都有“根本”的意思，也就是说很多东西是从原根发展、推导出来的。

况且在 OI-Wiki 中说道：

在抽象代数中，原根就是循环群的生成元．这个概念只在模 m 既约剩余系关于乘法形成的群中有「原根」这个名字，在一般的循环群中都称作「生成元」。并非每个模 m 既约剩余系关于乘法形成的群都是循环群，存在原根就表明它同构于循环群，如果不存在原根就表明不同构。

“生成元”这个名字够形象了——生成某些东西的原始起点。

所以原根就是与 n 互质的模 n 剩余类的生成起点。

性质

以下的内容比较庞大，如有错误烦请指出。

如下不会再使用一些非形式化语言，读者要对形式化语言有一个心理预期。

原根判定定理

定理：设 n>1 为正整数，g 为与 n 互素的整数。则 g 是模 n 的原根当且仅当对于 \varphi(n) 的每一个素因子 p，都有

g^{\frac{\varphi(n)}{p}}\not\equiv 1\pmod{n}.

证明：

必要性（\Rightarrow）：若 g 是原根，则 \delta_n(g)=\varphi(n)。对于任意素因子 p\mid\varphi(n)，显然 \frac{\varphi(n)}{p}<\varphi(n)。由阶的最小性定义，g^{\frac{\varphi(n)}{p}}\not\equiv 1\pmod{n} 必然成立。

充分性（\Leftarrow）：采用反证法。假设 g 满足题设条件但不是原根，则 \delta_n(g)<\varphi(n)。由前文已证的阶的性质 \delta_n(g)\mid\varphi(n)，可知存在正整数 d>1 使得 \varphi(n)=d\cdot\delta_n(g)。

取 d 的任一素因子 p，则 p\mid\varphi(n) 且 \delta_n(g)\mid\frac{\varphi(n)}{p}。于是

g^{\frac{\varphi(n)}{p}}=\left(g^{\delta_n(g)}\right)^{\frac{\varphi(n)}{p\cdot\delta_n(g)}}\equiv 1^{\frac{\varphi(n)}{p\cdot\delta_n(g)}}\equiv 1\pmod{n},

这与题设条件 "g^{\frac{\varphi(n)}{p}}\not\equiv 1" 矛盾。故必有 \delta_n(g)=\varphi(n)，即 g 是原根。证毕。

原根个数定理

定理：若模 n 存在原根，则模 n 的原根恰有 \varphi(\varphi(n)) 个。

证明：

设 g 是模 n 的一个原根，则 \delta_n(g)=\varphi(n)。考虑既约剩余系中所有元素可唯一表示为 g^k（其中 0\le k<\varphi(n)）——这是因为 \{g^0,g^1,\dots,g^{\varphi(n)-1}\} 这 \varphi(n) 个元素互不同余（若 g^i\equiv g^j\pmod{n} 且 0\le j<i<\varphi(n)，则 g^{i-j}\equiv 1，与阶为 \varphi(n) 矛盾），故构成完全既约剩余系。

对于任意 g^k，由前文已证的阶的计算公式：

\delta_n(g^k)=\frac{\delta_n(g)}{\gcd(\delta_n(g),k)}=\frac{\varphi(n)}{\gcd(\varphi(n),k)}.

因此，g^k 是原根当且仅当 \delta_n(g^k)=\varphi(n)，即

\frac{\varphi(n)}{\gcd(\varphi(n),k)}=\varphi(n)\iff \gcd(\varphi(n),k)=1.

在 0\le k<\varphi(n) 范围内，与 \varphi(n) 互素的 k 恰好有 \varphi(\varphi(n)) 个（由欧拉函数定义）。故原根个数为 \varphi(\varphi(n))。证毕。

原根存在定理

此定理非常重要，但分类讨论较多。

建议读者不要依赖于 OI-Wiki 的证明，要参考证明思想并自行证明一回。

下面是一处断言。

定理：模 n 存在原根当且仅当 n 具有下列四种形式之一：

n=2, n=4, n=p^k, n=2p^k

其中 p 为奇素数，k\ge 1 为正整数。

证明：

证毕。

大步小步与扩展大步小步

定义与作用

在无模数的运算中，我们求解 a^x=b 这么一个式子，是直接表示成 x=\log_{a}{b} 的，这就叫对数运算。实数域上的对数函数连续，于是实数域上的对数运算相对来说较容易计算。

但在模 m 的运算中，你发现对数是离散的，即不连续，这就直接导致形似 a^x\equiv b\pmod{m} 的这种同余方程难以用通用方式表达 / 解出。

于是，人类便发明了离散对数的求解算法，其中则有大步小步算法（Baby-Step Giant-Step, BSGS）。

普通大步小步算法可以在 O(\sqrt{m}) 的时间去求解 a^x\equiv b\pmod{m} 这个方程的解，其中 \gcd(a,m)=1,x\in[0,m)。

算法

先考虑朴素的算法，即把 x 从 0 向 m-1 进行枚举，显然这个过程中一定会得到一个合法解，时间复杂度 O(m)。

考虑采用分块的思想——即将部分单体处理转化为整体处理的，从而加快运算速度。

一般分块的块长是取根号的，即“块长”等于“块数”等于“原长度开根”，这样通常能达到很好的效果。

于是模仿这个思想，令 t=\lceil\sqrt{m}\rceil，则 x=At-B，其中 A,B\in[0,t]。

所以方程可化为 a^{At}\cdot a^{-B}\equiv b\pmod{m}\Rightarrow a^{At}\equiv a^{B}\cdot b\pmod{m}。

发现现在的同余式两边各只有最多 \sqrt{m} 级别的不同数字了，且两边变量 A,B 互不影响。

所以我们可以用容器建立映射关系，如果两边数值模 m 后匹配，那么就找到了一个合法解。

时间复杂度 O(\sqrt{m})，忽略常系数。

注意：BSGS 通常用来求出（正）整数解中最值，但并不意味着 BSGS 只能求最值解。

为什么普通大步小步要求 a,m 互质？

观察下面这个推导：

a^{At}\cdot a^{-B}\equiv b\pmod{m}\Rightarrow a^{At}\equiv a^{B}\cdot b\pmod{m}

这个式子其实也是需要满足反推的，因为得到解后要反推。

a^{At}\cdot a^{-B}\equiv b\pmod{m}\Leftrightarrow a^{At}\equiv a^{B}\cdot b\pmod{m}

所以 a^{B} 必须要保证有逆元，所以 \gcd(a^{B},m)=1\Leftrightarrow\gcd(a,m)=1。

扩展大步小步

由上文可知，当 \gcd(a,m) \neq 1 时，a 在模 m 下没有逆元，无法直接套用标准 BSGS。

于是，扩展大步小步算法（exBSGS）出现了！

exBSGS 的核心是通过逐层提取公因子，将问题转化为标准 BSGS 可解的形式，和扩展中国剩余定理两两拼接的思想有些类似。

算法详细流程

设当前方程为 a^x \equiv b \pmod{m}，维护一个累加偏移量 k=0（记录已被提取（公因子）的指数）。

迭代过程

最终解为 x = k + y（步骤七）。

注意：上面标注的步骤可能出现在下面的“exBSGS 正确性证明”中，请读者一定熟悉步骤 * 的指代内容。

exBSGS 正确性证明

请读者一定细细品鉴本处的证明，养成证明习惯与证明思维。

本处的证明也算是补充了 OI-Wiki 对于 exBSGS 正确性证明的不足。

定理 1

设 d = \gcd(a,m) 且 d > 1，d \mid b。则：

a^x \equiv b \pmod{m} \iff a^{x-1} \equiv \frac{b}{d} \cdot \left(\frac{a}{d}\right)^{-1} \pmod{\frac{m}{d}}

证明：

因为 $d \mid a$，$d \mid m$，$d \mid b$，设 $a = da'$，$m = dm'$，$b = db'$。 代入得 $(da')^x = db' + tdm'$，即 $d^{x-1}a'^x d = d(b' + tm')$。 两边除以 $d$：$d^{x-1}a'^x = b' + tm'$。 当 $x \geq 1$ 时，左边含因子 $d^{x-1}$，我们关注模 $m' = m/d$： $$d^{x-1}a'^x \equiv b' \pmod{m'}$$ 由于 $a = da'$，所以 $a' = a/d$。我们需要将 $a^{x-1}$ 表示出来： $$a^{x-1} \cdot a' = a^{x-1} \cdot \frac{a}{d} = \frac{a^x}{d}$$ 所以 $\frac{a^x}{d} \equiv \frac{b}{d} \pmod{\frac{m}{d}}$，即 $a^{x-1} \cdot \frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{m}{d}}$。 因为 $\gcd(a/d, m/d) = 1$（这是关键，因为 $\gcd(a/d, m/d) = \gcd(a,m)/d = 1$），所以 $a/d$ 在模 $m/d$ 下有逆元。 因此： $$a^{x-1} \equiv \frac{b}{d} \cdot \left(\frac{a}{d}\right)^{-1} \pmod{\frac{m}{d}}$$ $(\Leftarrow)$ 反向推导只需乘以 $a$ 并乘以 $d$，显然成立。$\blacksquare
定理 2

上述迭代过程必在有限步内终止，且终止时 \gcd(a, m_k) = 1。

证明：

每次迭代中，m_{i+1} = m_i / d_i，其中 d_i = \gcd(a, m_i) \geq 2（因为若 d_i=1 则停止）。

因此 m_{i+1} \leq m_i / 2，经过 O(\log m) 步后必有 m_k = 1 或 \gcd(a, m_k) = 1。

实际上，由于 d_i 包含 a 的所有尚未被"消去"的与 m_i 的公因子，最终必然使得 \gcd(a, m_k) = 1。\blacksquare

定理 3

设经过 k 次迭代后，用标准 BSGS 求得 a^y \equiv B \pmod{m_k} 的解为 y，则 x = k + y 是原方程的解。

证明：

由定理 1 的迭代应用，第 i 次迭代建立对应关系：

x_{i-1} = 1 + x_i

其中 x_{i-1} 是第 i-1 步方程的解，x_i 是第 i 步方程的解。

累加得 x_0 = k + x_k，其中 x_0 是原方程的解，x_k = y 是最终 BSGS 方程的解。

因此 x = k + y。\blacksquare

定理 4

若算法返回 x，则 x 是原方程的最小非负整数解。

证明：

算法在每次迭代中减去了 x 的 1 个单位（通过令 x' = x-1），总共减去 k。

最终 BSGS 求得的是 y \in [0, m_k) 内的最小解。

由对应关系，原解为 x = y + k。

假设存在更小的解 x' < x，则要么在迭代过程中提前遇到 b=1（已被检查），要么对应到最终 BSGS 的解 y' = x' - k < y，与 BSGS 的最小性矛盾。\blacksquare

定理 5

若算法在某个步骤三判定 d \nmid b 并返回无解，则原方程确实无解。

证明：

反设原方程有解 x。若当前处于第 k 层迭代，考虑原方程模 m_k 的最小非负剩余。

有 a^x \equiv b \pmod{m_k}。由于 d = \gcd(a, m_k) \nmid b，而左边 a^x 含因子 d（因为 x \geq k \geq 1），故 d \mid a^x，从而应有 d \mid b，矛盾。

特殊情况 x < k：这要求在前 k 次迭代中某次 x 已减至 0，即原方程解 x < k，但此时应已在步骤一中因 b \equiv 1 而被特判。\blacksquare

exBSGS 复杂度分析

迭代次数方面，每次 m 至少减半，故 O(\log m) 次；单次 BSGS 应该是 O(\sqrt{m_k}) \leq O(\sqrt{m})。

所以总时间复杂度是 O(\log m + \sqrt{m})，总空间复杂度 O(\sqrt{m})。

基于值域预处理的快速离散对数

该算法是用来高效解决下面问题的：

给定质数 P 以及它的一个原根 g。

有 q 组询问，每组询问给出整数 y，你需要找到最小的非负整数 x 使得 g^x\equiv y\pmod P。

该算法解决上面问题的理论时间复杂度为 O(\frac{P^{\frac{3}{4}}}{\log^{0.5}{P}}+q\log{P})，且该算法属于 BSGS 的扩展，在此算是给读者留一个思考，就不讲解了。

模意义下的单位根

给定正整数 m,k，若整数 x 满足 \gcd(x,m)=1,x^k\equiv1\pmod{m}，则称 x 是模 m 下的 k 次单位根。

高次剩余

参考文献声明

[1] Z. Cao, Q. Sha, and X. Fan, "Adleman-Manders-Miller root extraction method revisited," in Information Security and Cryptology (Inscrypt 2011), LNCS 7537, Berlin: Springer, 2012, pp. 77-85. DOI: 10.1007/978-3-642-34704-7_6

组合数学

组合数学部分，我们就不讲那些基础的了，我们只讲容斥与反演这两大难点。

容斥

小学奥数中对容斥的理解

先提出一个问题：

班里有 20 个喜欢语文的，有 60 个喜欢数学的，有 35 个喜欢物理的。

有 5 个人同时喜欢语文和数学，有 15 个人同时喜欢语文和物理，有 35 个人同时喜欢数学和物理。

有 1 个人同时喜欢语文、数学和物理。

请问班级里有几个人至少喜欢语文、数学、物理这三科中其中一科。

显然答案为 20+60+35-5-15-35+1=61。

具体地，如果用事件 A,B,C 来表示，则有 |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|。

小学奥数对容斥的理解，就是“奇加偶减”“奇减偶加”这类的口诀。

广义上的容斥

将上述直觉推广至 n 个集合的情形。设 A_1, A_2, \dots, A_n 为有限集，则：

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} \left|\bigcap_{i=1}^{n} A_i\right|

用更紧凑的记号可写为：

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \left|\bigcap_{i\in S} A_i\right|

概率形式：若 A_i 是事件，则

P\left(\bigcup_{i=1}^{n} A_i\right) = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} P\left(\bigcap_{i\in S} A_i\right)

这里的符号 (-1)^{|S|-1} 正是“奇加偶减”的代数体现——当交集的集合个数 |S| 为奇数时符号为正，偶数时为负。

凑容斥系数

概念

标准的容斥原理中，系数是固定的 (-1)^{|S|-1}。但在许多问题中，直接套用标准形式会导致复杂度爆炸（通常是 O(2^n)），或者难以直接计算交集的大小。

“凑容斥系数”的核心思想是：通过对容斥式子两边乘以一个设计的系数 f(|S|)，或对不同大小的子集赋予不同权重，使得最终式子能够方便求和，或者将难以计算的项相互抵消，从而得到一个闭式解或更高效的算法。

另一种常见场景是反问题：已知某些容斥和式的结果，需要反推出各个 |A_i| 或某个特定交集的大小。

Min-Max 容斥

最经典的凑系数应用之一是 Min-Max 容斥。

设 X = \{x_1, x_2, \dots, x_n\} 是一个有限数集，记：

则有恒等式：

\max(X) = \sum_{\emptyset \neq S \subseteq X} (-1)^{|S|-1} \min(S) \min(X) = \sum_{\emptyset \neq S \subseteq X} (-1)^{|S|-1} \max(S)

推导思路（凑系数的角度）：

考虑如何表示 \max(X)。对于任意元素 x \in X，x 对 \max(X) 有贡献当且仅当 x 是 X 中最大值。我们尝试用 \min(S) 的线性组合来表示：

\max(X) = \sum_{\emptyset \neq S \subseteq X} c_{|S|} \cdot \min(S)

其中 c_{|S|} 是仅依赖于集合大小的待定系数。

通过考察所有元素按大小排序后的贡献，可以解出 c_k = (-1)^{k-1}。具体地，假设 x_1 < x_2 < \dots < x_n，则 x_k 作为 \min(S) 出现的次数是 \binom{n-k}{|S|-1}（从比 x_k 大的 n-k 个元素中选 |S|-1 个）。于是 x_k 的总贡献系数为：

\sum_{j=1}^{n-k+1} c_j \binom{n-k}{j-1}

要让这个式子在 k=n（即最大值）时为 1，在 k<n 时为 0，需要满足：

\sum_{j=1}^{m} c_j \binom{m-1}{j-1} = [m=1]

令 d_j = c_j，利用二项式反演（后文会提到）可得 c_j = (-1)^{j-1}。

Min-Max 容斥例题选讲

先看题：

刚开始你有一个数字 0，每一秒钟你会随机选择一个 [0, 2^n − 1] 的数字，与你手上的数字进行或操作。选择数字 i 的概率是 p_i。保证 0 \le p_i \le 1,\sum p_i = 1。

问期望多少秒后，你手上的数字变成 2^n − 1。

对于 100\% 的数据，n \le 20。

设 T 为手上的数字变成 2^n-1（即所有 n 位都变为 1）的所需时间。

对于第 i 位（0 \leq i < n），设 T_i 为该位首次被或上的时间。显然：

T = \max(T_0, T_1, \dots, T_{n-1})

直接计算 \mathbb{E}[\max(T_i)] 很困难，因为 T_i 之间不是独立的（一个数字可能同时设置多位）。但使用 Min-Max 容斥：

\mathbb{E}[T] = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \mathbb{E}\left[\min_{i \in S} T_i\right] 这是一个几何分布： - **成功事件**：选中的数字 $x$ 满足 $x \& S \neq 0$（即 $x$ 在 $S$ 包含的某一位上为 $1$） - **成功概率**：$P(S) = \sum_{x: (x \& S) \neq 0} p_x

因此：

\mathbb{E}\left[\min_{i \in S} T_i\right] = \frac{1}{P(S)}

直接计算 P(S) 需要对 O(2^n) 个 x 求和。利用补集转化：

P(S) = 1 - \sum_{x: (x \& S) = 0} p_x = 1 - \sum_{x \subseteq \overline{S}} p_x

其中 \overline{S} 是 S 的补集（在 n 位下的按位取反）。

所以我们只需计算子集和：

f[mask] = \sum_{x \subseteq mask} p_x

这可以通过高维子集前缀和（后文会讲到）在 O(n \cdot 2^n) 内完成。

推荐习题

Luogu P3349 [ZJOI2016] 小星星

反演

二项式反演

这应该是所有组合数反演中最简单的一个反演了。

先举个例子吧。

错排问题
问题概念

有 n 个人站在 n 个位置上，第 i 个人如果站在第 i 个位置上我们认为他站对了，否则认为站错了。

求有多少站法使得所有人站错。

概念设计

我们设 g_n 表示 n 个人随便站的方案数，f_k 表示 k 个人恰好都站错的方案数，即错排数。

然后的部分不太好理解。

接下来我们要总结出 g_n 与 f_k 的关系。

我们知道，g_n 实际上等于 n!，这包含了 1 到 n 排列的所有情况。

而在这些排列中，总有至少 0 个、至多 n 个点，它们的数值与它们的坐标值一样，我们称这种点为固定点。不是固定点的点，我们就称其为动点。

接下来我们发现，一个合法排列的动点集合，组成了一个错排。

那么接下来我们就能总结出 g_n 与 f_k 的关系了！我们设有 k 个动点，这些动点组成一个 k 错排，那么剩下的固定点数量就为 n - k，这些点的所有可能是可以通过组合数公式提前确定的，即 \binom{n}{n-k}。

初步推出

显然有：

g_n = \sum_{k = 0}^{n}\binom{n}{n - k}f_k

又因为 \binom{n}{n-k} = \binom{n}{k}，所以有：

g_n = \sum_{k = 0}^{n}\binom{n}{k}f_k

注意！这个公式很重要！

推导 / 证明

二项式反演有很多种证明 / 推导方法，但这里只介绍一种，在普遍情况下也只需要记住一种证明 / 推导方法。

那么，接下来我们开始推导（这里假定读者掌握了二项式定理）。

解：有

f_n = \sum_{k = 0}^{n}[n - k = 0]\binom{n}{k}f_k \\ g_n = \sum_{k = 0}^{n}\binom{n}{k}f_k

结合二项式系数，易得

\sum_{i = 0}^{n}(-1)^{i}\binom{n}{i} = [n = 0]

带入，易得

f_n = \sum_{k = 0}^{n}\sum_{m = 0}^{n - k}(-1)^{m}\binom{n - k}{m}\binom{n}{k}f_k

注意到

\begin{aligned} \binom{n - k}{m}\binom{n}{k} &= \frac{(n - k)!}{m!(n - m - k)!} \cdot \frac{n!}{k!(n - k)!} \\ &= \frac{1}{\frac{n!m!}{\prod_{i = n - m - k + 1}^{n}{i}}} \cdot \frac{n!}{k!} \\ &= \frac{\prod_{i = n - m - k + 1}^{n}{i}}{n!m!} \cdot \frac{n!}{k!} \\ &= \frac{\prod_{i = n - m - k + 1}^{n}{i}}{m!k!} \\ &= \frac{n!}{m!k!(n - m - k)!} \\ &= \frac{n!}{m!(n - m)!} \cdot \frac{(n - m)!}{k!(n - m - k)!} \\ &= \binom{n}{m}\binom{n - m}{k} \end{aligned}

则有

\begin{aligned} f_n &= \sum_{k = 0}^{n}\sum_{m = 0}^{n - k}(-1)^{m}\binom{n}{m}\binom{n - m}{k}f_k \\ &= \sum_{m = 0}^{n}(-1)^{m}\binom{n}{m}\sum_{k = 0}^{n - m}\binom{n - m}{k}f_k \\ &= \sum_{m = 0}^{n}(-1)^{m}\binom{n}{m}g_{n - m} \end{aligned}

得出

f_n = \sum_{m = 0}^{n}(-1)^{n - m}\binom{n}{m}g_m

结束，得出结论：g_n = \sum_{k = 0}^{n}\binom{n}{k}f_k \Leftrightarrow f_n = \sum_{m = 0}^{n}(-1)^{n - m}\binom{n}{m}g_m。

近似地，我们可以得出两条结论，即二项式反演公式：

g_n = \sum_{k = 0}^{n}\binom{n}{k}f_k \Leftrightarrow f_n = \sum_{m = 0}^{n}(-1)^{n - m}\binom{n}{m}g_m \\ g_k = \sum_{i = k}^{n}\binom{i}{k}f_i \Leftrightarrow f_k = \sum_{j = k}^{n}(-1)^{j - k}\binom{j}{k}g_j

其中第一式的 g_i 表示“至多”，第二式的 g_i 表示“至少”。

在两式中，f_i 均表示“恰好”。

也就是说，通过二项式反演，我们实现“至多”/“至少”和“恰好”的转化。

例题

由于二项式反演的合适例题稀少，因此只讲下面这一道题。

例题：Luogu P4859 已经没有什么好害怕的了。

题意概括：

给出 n 个数 a_{i} 和 n 个数 b_{i}，要求将 a 序列和 b 序列中数两两配对，使得 a>b 的对数减去 a<b 的对数等于 k。

可以看出期望时间复杂度是 O(n^2) 的。

设 a>b 的对数与 a<b 的对数分别为 t_1,t_2，则 \begin{cases}t_1+t_2=n\\t_1-t_2=k\end{cases}，得到 t_1=\frac{n+k}{2}。

所以问题转化为了求令 t_1 恰好为 k' 的方案数。

考虑朴素做法：对 a,b 进行排序，然后考虑 a_i 的匹配。

你会发现，当 a_i 匹配到了一个比它本身大的数，你是无法判断到底匹配了哪个 b 中元素的，从而你无法判断到底哪个 j>i 的位置的 a_j 的匹配会受到影响，总之就是朴素做法很困难。

但要是让 a_i 匹配一个比它小的数呢？对于任意的 j<i，a_j 的匹配数已经处理完毕了，无影响；对于任意的 j>i，你会发现可选方案全都受到了本变动的影响，从而不存在匹配较大数所产生的“位置不同，影响不同”的情况。

所以，我们发现动态规划是可以计算“至少有 k' 个 a>b 的串”的方案数的。

我们设 f_{i,j} 表示“考虑到第 i 位，有 j 个 a>b 的串”的方案数。

考虑到反演。

先令 g_{i}=(n-i)!\cdot f_{n,i}，然后套用二项式反演：f_k = \sum_{j = k}^{n}(-1)^{j - k}\binom{j}{k}g_j，把“至少”向“恰好”转化即可。

高维子集前缀和

为什么要把高维子集前缀和拿出来单独讲呢？因为其是在学习子集反演时所必须知道的前置知识。

正是因为它的重要性，才会把它拿出来讲。

思考一个问题：

给定一个 k 维 0/1 数组（或视为长度为 2^k 的数组），设 f[mask] 表示状态 mask 的值。

要求计算：

F[mask] = \sum_{submask \subseteq mask} f[submask]

即对于每个 mask，求出它的所有子集的 f 值之和。

这个问题朴素做法是 O(3^k) 的，显然不行，所以我们要借用高维前缀和的思想。

即：固定其他维度，先专注于一个维度上的单独前缀和。如此，对所有维度依次进行此操作即可。

定义 dp[i][mask] 为：只考虑 mask 的前 i 位，所有满足 submask \subseteq mask 且 submask 与 mask 只在前 i 位可能有差异的子集之和。

状态转移：

DP 公式：dp[i][mask] = dp[i-1][mask] + [mask_i=1] \cdot dp[i-1][mask \oplus 2^i]（其中 [\dots] 表示艾弗森括号，内部表达式成立时取值 1，否则取值 0。

观察到转移时第一维只与 i-1 产生依赖，所以可以滚动数组优化掉第一维。

时间复杂度 O(k\cdot2^k)，空间复杂度 O(2^k)。

高维差分同理。

子集反演

先给出子集反演的内容：

若

\displaystyle F[S] = \sum_{T \subseteq S} G[T]

则

\displaystyle G[S] = \sum_{T \subseteq S} (-1)^{|S|-|T|} F[T]
证明

有一个前置的恒等式：

\sum_{T \subseteq X} (-1)^{|T|} = [|X| = 0] = \begin{cases} 1, & X = \emptyset \\ 0, & X \neq \emptyset \end{cases}

该式成立是因为对非空集合 X，其偶数大小子集与奇数大小子集个数相等（二项式定理 (1-1)^{|X|} = 0）。

证明过程：

我们要证：若 \displaystyle F[S] = \sum_{T \subseteq S} G[T]，则 \displaystyle G[S] = \sum_{T \subseteq S} (-1)^{|S|-|T|} F[T]。

从 G[S] 出发，利用上述恒等式进行"筛选"：

G[S] &= \sum_{T \subseteq S} \big[ |S \setminus T| = 0 \big] \cdot G[T] \quad \\ &= \sum_{T \subseteq S} \left( \sum_{P \subseteq S \setminus T} (-1)^{|P|} \right) G[T] \quad \\ &= \sum_{T \subseteq S} \sum_{\substack{P \subseteq S \\ T \cap P = \emptyset}} (-1)^{|P|} G[T] \end{aligned}

交换求和顺序，改为先枚举 P，再枚举与 P 不相交的 T（即 T \subseteq S \setminus P）：

= \sum_{P \subseteq S} (-1)^{|P|} \left( \sum_{T \subseteq S \setminus P} G[T] \right)

注意到内层求和正是 F[S \setminus P]（由已知条件 F[X] = \sum_{T \subseteq X} G[T]），因此：

= \sum_{P \subseteq S} (-1)^{|P|} F[S \setminus P]

令 U = S \setminus P，则当 P 取遍 S 的所有子集时，U 也取遍 S 的所有子集，且 |P| = |S| - |U|，代入得：

G[S] &= \sum_{U \subseteq S} (-1)^{|S| - |U|} F[U] \\ &= \sum_{T \subseteq S} (-1)^{|S| - |T|} F[T] \end{aligned}

证毕。

子集反演例题

例题：AtCoder arc101_c [ARC101E] Ribbons on Tree

例题讲解：

先给出概括题意：

给定一个大小为 n 的树，保证 n 为偶数且小于 5000。

你需要给树上的点两两配对，对于一组对子 (u, v)，在树上将 u\rightarrow v 的路径染色，定义一个配对方案合法当且仅当所有边都有颜色。

求方案数对 10^9 + 7 取模。

首先可得正解期望时间复杂度 o(n^2)，显然要有树形 DP。

又由于这是子集反演例题，所以显然要有子集反演。

可以想到，设 F(S) 表示至少 S 集合中的边没有被染色的方案数。

子集反演得 ans=\sum_{S\subseteq T}(-1)^{|S|}F(S)。

考虑 DP 计算 ans。设 f(x, i) 表示：当前在点 x，和 x 相连的连通块大小是 i 的 DP 值。

每次考虑一条边是否加入集合 S，讨论是加入还是不加入，在加入的时候乘上连通块内点任意匹配的方案数即可。

第二类斯特林数

第二类斯特林数（Stirling Numbers of the Second Kind）是组合数学中的重要概念，记作 S(n,k) 或 \displaystyle{n \brace k}。

定义

第二类斯特林数表示将 n 个有区别的元素划分成 k 个无区别的非空集合的方案数。换句话说，它计算的是将 n 个不同元素分成 k 个非空子集的划分方式数目。

等价描述：将 n 个有标号的球放入 k 个无标号的盒子中，要求盒子非空，其方案数即为第二类斯特林数。

递推公式

第二类斯特林数满足以下递推关系：

{n \brace k} = {n-1 \brace k-1} + k \cdot {n-1 \brace k}

其中边界条件为：

{n \brace 0} = \begin{cases} 1, & n = 0 \\ 0, & n > 0 \end{cases} {n \brace n} = 1, \quad \forall n \geq 0
递推公式证明

考虑第 n 个元素的归属，有两种情况：

由加法原理，递推公式得证。

显式公式

第二类斯特林数的显式公式（容斥原理）：

{n \brace k} = \frac{1}{k!} \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n
显式公式证明

考虑从 n 元集合到 k 元集合的满射函数个数。

首先，不考虑满射条件，从 n 元集合到 k 元集合的函数共有 k^n 个。

设 A_i 表示不映射到第 i 个元素的函数集合。由容斥原理：

|\overline{A_1} \cap \cdots \cap \overline{A_k}| = \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n

这恰好是满射函数的个数。由于 k 个盒子是无区别的，需要除以 k!，即得显式公式。

特殊值
{n \brace 1} = 1, \quad \forall n \geq 1 {n \brace 2} = 2^{n-1} - 1 {n \brace n-1} = \binom{n}{2}

第一类斯特林数

第一类斯特林数（Stirling Numbers of the First Kind）分为无符号和有符号两种形式。

无符号第一类斯特林数

无符号第一类斯特林数记作 c(n,k) 或 \displaystyle \left[\begin{matrix} n \\ k \end{matrix}\right]，表示将 n 个不同元素划分成 k 个非空循环排列（圆排列）的方案数。

递推公式
c(n,k) = (n-1) \cdot c(n-1,k) + c(n-1,k-1)
递推公式证明

考虑第 n 个元素的归属：

  1. 第 n 个元素单独构成一个圆排列：方案数为 c(n-1,k-1)。

  2. 第 n 个元素插入到已有的圆排列中：前 n-1 个元素已形成 k 个圆排列，第 n 个元素可以插入到任意元素的左侧，共有 n-1 个位置，方案数为 (n-1) \cdot c(n-1,k)。

有符号第一类斯特林数

有符号第一类斯特林数记作 s(n,k)，定义为：

s(n,k) = (-1)^{n-k} \cdot c(n,k)
与下降阶乘的关系

有符号第一类斯特林数是下降阶乘 (x)_n = x(x-1)(x-2)\cdots(x-n+1) 展开式中 x^k 的系数：

(x)_n = \sum_{k=0}^{n} s(n,k) \cdot x^k
与上升阶乘的关系

无符号第一类斯特林数是上升阶乘 \langle x \rangle_n = x(x+1)(x+2)\cdots(x+n-1) 展开式中 x^k 的系数：

\langle x \rangle_n = \sum_{k=0}^{n} c(n,k) \cdot x^k

斯特林数的相关性质

幂次展开性质

第二类斯特林数可以将普通幂转换为下降阶乘：

x^n = \sum_{k=0}^{n} {n \brace k} \cdot (x)_k

其中 (x)_k = x(x-1)\cdots(x-k+1) 为下降阶乘。

求和性质

贝尔数与第二类斯特林数的关系：

B_n = \sum_{k=0}^{n} {n \brace k}

贝尔数 B_n 表示将 n 元集合划分成任意个非空子集的方案数。

正交关系

两类斯特林数满足以下正交关系：

\sum_{k=m}^{n} {n \brace k} \cdot s(k,m) = \delta_{n,m} \sum_{k=m}^{n} s(n,k) \cdot {k \brace m} = \delta_{n,m}

其中 \delta_{n,m} 是克罗内克函数，当 n=m 时为 1，否则为 0。

生成函数

第二类斯特林数的指数生成函数：

\sum_{n=k}^{\infty} {n \brace k} \frac{z^n}{n!} = \frac{(e^z - 1)^k}{k!}

第一类斯特林数的指数生成函数：

\sum_{n=k}^{\infty} c(n,k) \frac{z^n}{n!} = \frac{(-\ln(1-z))^k}{k!}

斯特林数的相关证明

下面将证明一些斯特林数的相关性质。

幂次展开性质的证明

定理：对于任意非负整数 n，有

x^n = \sum_{k=0}^{n} {n \brace k} \cdot (x)_k

证明（数学归纳法）：

当 n=0 时，左边 x^0 = 1，右边 \displaystyle{0 \brace 0} \cdot (x)_0 = 1 \cdot 1 = 1，成立。

假设对 n-1 成立，即 \displaystyle x^{n-1} = \sum_{k=0}^{n-1} {n-1 \brace k} \cdot (x)_k。

对于 n，利用 (x)_k \cdot x = (x)_k \cdot ((x-k)+k) = (x)_{k+1} + k \cdot (x)_k，有：

\begin{aligned} x^n &= x \cdot x^{n-1} = \sum_{k=0}^{n-1} {n-1 \brace k} \cdot x \cdot (x)_k \\ &= \sum_{k=0}^{n-1} {n-1 \brace k} \cdot ((x)_{k+1} + k \cdot (x)_k) \\ &= \sum_{k=1}^{n} {n-1 \brace k-1} \cdot (x)_k + \sum_{k=0}^{n-1} k \cdot {n-1 \brace k} \cdot (x)_k \\ &= \sum_{k=0}^{n} \left( {n-1 \brace k-1} + k \cdot {n-1 \brace k} \right) (x)_k \\ &= \sum_{k=0}^{n} {n \brace k} \cdot (x)_k \end{aligned}

证毕。

正交关系的证明

定理：

\sum_{k=m}^{n} {n \brace k} \cdot s(k,m) = \delta_{n,m}

证明：

由幂次展开性质：

x^n = \sum_{k=0}^{n} {n \brace k} \cdot (x)_k

又由第一类斯特林数的定义：

(x)_k = \sum_{m=0}^{k} s(k,m) \cdot x^m

代入得：

\begin{aligned} x^n &= \sum_{k=0}^{n} {n \brace k} \sum_{m=0}^{k} s(k,m) \cdot x^m \\ &= \sum_{m=0}^{n} \left( \sum_{k=m}^{n} {n \brace k} \cdot s(k,m) \right) x^m \end{aligned}

比较两边 x^m 的系数，当 m=n 时系数为 1，否则为 0，即得正交关系。

证毕。

斯特林反演

斯特林反演——比较冷门，知道有这么一个东西就很好了。

斯特林反演公式

设 f(n) 和 g(n) 是两个数列，则以下两个命题等价：

命题 A：

f(n) = \sum_{k=0}^{n} {n \brace k} \cdot g(k)

命题 B：

g(n) = \sum_{k=0}^{n} s(n,k) \cdot f(k)

注意：斯特林反演还有另外一种公式形式，如下：

f(n) = \sum_{k=n}^{\infty} {k \brace n} g(k) \quad \Longleftrightarrow \quad g(n) = \sum_{k=n}^{\infty} (-1)^{k-n} {k \brack n} f(k)

从线性代数角度看，其实该公式与上公式差别不是特别大，这里不证明。

对斯特林反演公式的证明

证明命题 A \Rightarrow 命题 B：

假设 \displaystyle f(n) = \sum_{k=0}^{n} {n \brace k} \cdot g(k) 成立。

考虑 \displaystyle\sum_{k=0}^{n} s(n,k) \cdot f(k)，代入 f(k) 的表达式：

\sum_{k=0}^{n} s(n,k) \cdot f(k) = \sum_{k=0}^{n} s(n,k) \sum_{m=0}^{k} {k \brace m} \cdot g(m)

交换求和顺序：

= \sum_{m=0}^{n} g(m) \sum_{k=m}^{n} s(n,k) \cdot {k \brace m}

由正交关系 \displaystyle\sum_{k=m}^{n} s(n,k) \cdot {k \brace m} = \delta_{n,m}

= \sum_{m=0}^{n} g(m) \cdot \delta_{n,m} = g(n)

同理可证 B \Rightarrow A。

证毕。

斯特林反演例题

例题：BZOJ4671 异或图

单位根反演

单位根

单位根的定义，或者说意义，就是 z^{n}=1 在复平面上的 n 个解。

单位根的几何意义理解其实很简单。对于 n 次单位根，你可以将其视为复平面上的一个内切正 n 边形，但是这个正 n 边形一定要有一个落在实轴上的顶点（根）。

你根据三角函数就可以推出，n 次单位根为如下形式：

\omega_{n}^{k} = \cos\frac{2\pi k}{n} + i\sin\frac{2\pi k}{n} = e^{i \cdot 2\pi k/n}, \quad k = 0, 1, \dots, n-1

然后，n 次单位根有以下几个基本性质：

单位根重要性质

给出结论

\frac{1}{n}\sum_{j=0}^{n-1} \omega_{n}^{jk} = [n \mid k]

这里默认 \omega_{n} 为我们优先选择的 n 次本原单位根 w_{n}^{1}（因为其能生成所有的 n 次单位根）。

下面给出证明：

分两种情况

情况一：n \mid k

此时 k = mn（m 为整数），所以

\omega^{jk} = \omega^{j \cdot mn} = (\omega^n)^{jm} = 1^{jm} = 1

每一项都是 1，因此

\frac{1}{n}\sum_{j=0}^{n-1} 1 = \frac{n}{n} = 1

情况二：n \nmid k

此时 \omega^k \neq 1。令 q = \omega^k，则求和变为

S = \sum_{j=0}^{n-1} q^j

这是一个等比级数，公比 q \neq 1，直接套公式：

S = \frac{q^n - 1}{q - 1} = \frac{(\omega^k)^n - 1}{\omega^k - 1} = \frac{(\omega^n)^k - 1}{\omega^k - 1} = \frac{1^k - 1}{\omega^k - 1} = \frac{0}{\omega^k - 1} = 0

分母 \omega^k - 1 \neq 0（因为 n \nmid k），所以合法。

因此

\frac{1}{n} S = 0

合并结论

\frac{1}{n}\sum_{j=0}^{n-1} \omega^{jk} = \begin{cases} 1, & n \mid k \\ 0, & n \nmid k \end{cases} = [n \mid k]

证毕。

单位根反演公式

设 F(x) 是一个 m 次多项式，F(x) = \sum_{i=0}^{m} f_i x^i，那么有：

\sum_{k=0}^{m} [n \mid k] f_k = \frac{1}{n} \sum_{i=0}^{n-1} F(\omega_n^i)

其中 \omega_n 是 n 次本原单位根，[n \mid k] 是艾弗森括号，当 n \mid k 时为 1，否则为 0。

这个公式的含义是：要从多项式 F(x) 的系数中筛选出下标被 n 整除的项之和，只需将 n 个单位根逐一代入 F，再取平均即可。

这个式子提示我们，求下标是某个数倍数的项的系数和可能不好求，但是如果这个多项式整体求值很好求，我们可以考虑利用这个式子求解。

单位根反演例题

例题：LJJ 学二项式定理。

题意：

一共有 T 组数据，每组数据如下：

输入以下变量的值：n, s, a_0, a_1, a_2, a_3，求以下式子的值：

\left[ \sum_{i=0}^{n} \left( \binom{n}{i} \cdot s^{i} \cdot a_{i \bmod 4} \right) \right] \bmod 998244353

讲解：

化出式子：

\sum_{j=0}^{3} a_j \sum_{i=0}^{n} \binom{n}{i} s^i [4 \mid (i-j)]

如何转向单位根反演

观察内层求和，对于固定的 j，它是：

\sum_{i=0}^{n} \binom{n}{i} s^i [4 \mid (i-j)]

这就是要从多项式 F(x) = \sum_{i=0}^{n} \binom{n}{i} x^i = (1+x)^n 的展开中，筛选出下标 i 满足 i \equiv j \pmod{4} 的项。

套用单位根反演公式，将 [4 \mid (i-j)] 替换：

[4 \mid (i-j)] = \frac{1}{4} \sum_{t=0}^{3} \omega_4^{t(i-j)}

其中 \omega_4 = e^{i\pi/2} = i（即虚数单位），四次本原单位根。

代入内层求和：

\sum_{i=0}^{n} \binom{n}{i} s^i \cdot \frac{1}{4}\sum_{t=0}^{3} \omega_4^{t(i-j)} = \frac{1}{4}\sum_{t=0}^{3} \omega_4^{-tj} \sum_{i=0}^{n} \binom{n}{i} (s \cdot \omega_4^t)^i

内层恰好是二项式定理：

\sum_{i=0}^{n} \binom{n}{i} (s \cdot \omega_4^t)^i = (1 + s\omega_4^t)^n

所以整个式子变为：

\sum_{j=0}^{3} a_j \cdot \frac{1}{4} \sum_{t=0}^{3} \omega_4^{-tj} (1+s\omega_4^t)^n

由于 \omega_4 = i，四个单位根就是 1, i, -1, -i，最终只需计算四个值 (1+s)^n,(1+si)^n,(1-s)^n,(1-si)^n，一切都变成了可直接计算的封闭形式。

多项式

（挖个坑）