专栏文章

可能你想学（2）——集合等离散数学

MMatrix_J
算法·理论参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
2 份
快照标识符
@mk8k07vi
此快照首次捕获于
2026/01/11 01:03
上个月
此快照最后确认于
2026/02/19 01:22
10 小时前
查看原文

前言

上一章：点这里
哇塞，作者可真是一只大鸽子，鸽了一个月。 😔
不难注意到上篇是考试后发的，那么这篇也是。😮
本章将讲述集合等离散数学内容。😊
不涉及代码问题，只讲述基础数学内容。

集合

集合的概念

集合是由不同对象聚集而成的一个整体，称其中的对象为成员或元素。若一个对象 ss 是集合 SS 中的一个成员，则可以写作 s∈Ss\in S，反之可以写作 s∉Ss\notin S。
集合中不能出现多个相同的元素，且集合是无序的。当两个集合 AA 和 BB 包含相同的元素时，称集合 AA 与 BB 是相等的，写作 A=BA=B。
我们采用下列特殊的符号来表示常见的集合
  • ∅\varnothing 表示空集，即集合中不含任何元素。
  • Z\mathbb{Z} 表示整数集。
  • R\mathbb{R} 表示实数集。
  • N\mathbb{N} 表示自然数集，N+\mathbb{N}^+ （或 N∗\mathbb{N}^*）表示正整数集。
对一个具体的集合而言，可以用列举法或描述法给出它的准确而清晰的表示。

列举法

可以在一对大括号内写出该集合内的元素，如 S={1,2,3}S=\{1,2,3\}。

描述法

基于以下的概括原则：
对任给的性质 PP，存在一个集合 SS，它的元素恰好是具有性质 PP 的所有对象，即 S={x∣P(x)}S=\{x \big| P(x)\} 其中 P(x)P(x) 表示 “xx 具有性质 PP”。
集合元素个数为有限数的集合为有限集，个数为无穷数的集合为无限集。如果有限集 AA 的元素个数为 nn，则称 AA 为 nn 元集，记作 ∣A∣=n\lvert A\rvert=n。

集合与集合之间的关系

在两个集合的关系中，子集是一个非常重要的概念。下面给出概念：
  • 子集：A⊆B⇔A\subseteq B \Leftrightarrow 对任意 x∈Ax\in A，都有 x∈Bx\in B。
  • 真子集：A⫋B⇔A⊆BA \subsetneqq B \Leftrightarrow A\subseteq B 且存在 x′∈Bx'\in B，但 x′∉Ax'\notin A。
  • 集合相等：A=B⇔A⊆BA=B \Leftrightarrow A\subseteq B，且 B⊆AB\subseteq A。（与上面的集合相等相同）
易知两个集合之间的关系的如下性质：
  • ∅⫋A(A≠∅)\varnothing \subsetneqq A (A \ne \varnothing)。
  • A⊆B,B⊆C⇒A⊆CA\subseteq B,B\subseteq C \Rightarrow A\subseteq C。
  • nn 元集 AA 总共有 2n2^n 个不同的子集。

集合之间的运算

集合的交集、并集、补集是通过元素与几何的关系来定义的：
  • 交集：C=A∩BC=A \cap B，其中 CC 中的任意一个元素 xx 满足 x∈Ax\in A 且 x∈Bx\in B。
  • 并集：C=A∪BC=A \cup B，其中 CC 中的任意一个元素 xx 满足 x∈Ax\in A 或 x∈Bx\in B。
  • 差集：C=A−BC=A-B，其中 CC 中的任意一个元素 xx 满足 x∈Ax\in A 且 x∉Bx\notin B。
  • 补集：给定一个集合 UU，称 UU 为全集，且 A⊆UA\subseteq U，则定义集合 AA 的补集为 A‾=U−A\overline{A}=U-A。其中的元素 xx 满足 x∈Ux\in U 且 x∉Ax\notin A。
记 UU 为全集，容易证明集合的运算满足一下法则：
  • 等幂律：A∩A=A,A∪A=AA\cap A=A,A\cup A=A。
  • 同一律：A∩U=A,A∪U=U,A∩∅=∅,A∪∅=AA\cap U=A,A\cup U=U,A\cap \varnothing=\varnothing,A\cup\varnothing=A。
  • 互补律：A∩A‾=∅,A∪A‾=UA\cap\overline{A}=\varnothing,A\cup\overline{A}=U。
  • 交换律：A∩B=B∩A,A∪B=B∪AA\cap B=B\cap A,A\cup B=B\cup A。
  • 结合律：A∩(B∩C)=(A∩B)∩C,A∪(B∪C)=(A∪B)∪CA\cap(B\cap C)=(A\cap B)\cap C,A\cup(B\cup C)=(A\cup B)\cup C。
  • 分配律：A∩(B∪C)=(A∩B)∪(A∩C),A∪(B∩C)=(A∪B)∩(A∪C)A\cap(B\cup C)=(A\cap B)\cup (A\cap C),A\cup(B\cap C)=(A\cup B)\cap (A\cup C)。
  • 吸收律：A∪(A∩B)=A,A∩(A∪B)=AA\cup (A\cap B)=A,A\cap(A\cup B)=A。
  • 反演律（摩根律）：A∩B‾=A‾∪B‾,A∪B‾=A‾∩B‾\overline{A\cap B}=\overline{A}\cup\overline{B},\overline{A\cup B}=\overline{A}\cap\overline{B}。

容斥原理

容斥原理：
∣⋃i=1nAi∣=∑i=1n∣Ai∣−∑1≤i<j≤n∣Ai∩Aj∣+∑1≤i<j<k≤n∣Ai∩Aj∩Ak∣+⋯+(−1)n−1∣⋂i=1nAi∣\big|\bigcup\limits_{i=1}^n A_i\big|=\sum\limits_{i=1}^n\big|A_i|-\sum\limits_{1\le i<j\le n}\big|A_i\cap A_j\big|+\sum\limits_{1\le i<j<k\le n}\big| A_i\cap A_j\cap A_k\big|+\dots+(-1)^{n-1}\big|\bigcap\limits_{i=1}^n A_i\big|
一般用来计算至少具有某几个性质之一的元素个数。
作者在 2025 CSP-S 第一轮错误地使用了该原理，导致暴毙两分。 😟

原理证明

采用数学归纳法进行证明：
当 n=2n=2 时，设 A1∩A2=BA_1\cap A_2=B，A1′=A1−BA_1'=A_1-B，A2′=A2−BA_2'=A_2-B，则
A1∪A2=A1′∪A2′∪BA_1\cup A_2=A_1'\cup A_2'\cup B
同时，有 ∣A1′∣=∣A1∣−∣B∣\big| A_1'\big|=\big| A_1\big|-\big| B\big|，∣A2′∣=∣A2∣−∣B∣\big| A_2'\big|=\big| A_2\big|-\big| B\big|，故
∣A1∪A2∣=∣A1′∪A2′∪B∣=∣A1′∣+∣A2′∣+∣B∣=(∣A1∣−∣B∣)+(∣A2∣−∣B∣)+∣B∣=∣A1∣+∣A2∣−∣A1∩A2∣\begin{aligned} \big| A_1\cup A_2\big| &=\big| A_1'\cup A_2'\cup B\big| =\big|A_1'\big|+\big| A_2'\big|+\big| B\big| \\ &=(\big| A_1\big|-\big| B\big|)+(\big| A_2\big|-\big| B\big|)+\big| B\big| \\ &=\big| A_1\big|+\big| A_2\big|-\big| A_1\cap A_2\big|\end{aligned}
即当 n=2n=2 时结论成立。
若当 n=kn=k 时结论成立，则
&=\big|\bigcup\limits_{i=1}^{k}A_i\big|+\big|A_{k+1}\big|-\big|\big(\bigcup\limits_{i=1}^{k}A_i\big)\cap A_{k+1} \big| \\ &=\big|\bigcup\limits_{i=1}^{k}A_i\big|+\big|A_{k+1}\big|-\big|\bigcup\limits_{i=1}^{k}(A_i\cap A_{k+1} )\big| \\ &=\sum\limits_{i=1}^k\big| A_i\big|-\sum\limits_{1\le i<j \le k} \big|A_i \cap A_j\big|+\dots \\ &+(-1)^{k-1}\big|\bigcap\limits_{i=1}^kA_i\big| + \big|A_{k+1}\big|-\sum\limits_{i=1}^k\big| A_i\cap A_{k+1}\big| \\ &+\sum\limits_{1\le i<j \le k} \big|(A_i \cap A_{k+1})\cap(A_j\cap A_{k+1})\big|-\dots+(-1)^{k}\big|\bigcap\limits_{i=1}^k(A_i\cap A_{k+1})\big| \\ &=\sum\limits_{i=1}^{k+1}\big|A_i|-\sum\limits_{1\le i<j\le k+1}\big|A_i\cap A_j\big|+\dots+(-1)^{k}\big|\bigcap\limits_{i=1}^{k+1} A_i\big|\end{aligned} $$ 即当 $n=k+1$ 时成立。 有归纳原理知，对任意正整数 $n$，结论成立。 ### 逐步淘汰原理 另 $U$ 为全集，利用摩根定律 $$\overline{(\bigcup\limits_{i=1}^nA_i)}=\bigcap\limits_{i=1}^n(\overline{A_i})$$ 及公式 $\overline{A}=U-A$，改写容斥原理，得到下面的逐步淘汰原理： $$\begin{aligned} \big|\bigcap\limits_{i=1}^n(\overline{A_i})\big| &= \big| \overline{(\bigcup\limits_{i=1}^nA_i)}\big| = \big|U\big|-\big| \bigcup\limits_{i=1}^n A_i\big| \\ &= \big|U\big|-\sum\limits_{i=1}^n\big|A_i|+\sum\limits_{1\le i<j\le n}\big|A_i\cap A_j\big| \\ &-\sum\limits_{1\le i<j<k\le n}\big| A_i\cap A_j\cap A_k\big|+\dots+(-1)^{n}\big|\bigcap\limits_{i=1}^n A_i\big|\end{aligned} $$ 此公式又称为筛法公式，一般用来计算不具有某几个性质的任何一个性质的元素个数。 ~~组合等下一章再来。~~ # 图论 ## 图的基本定义 图：一张图 $G$ 和连接这些点的边构成，点的集合称为点集 $V$，变的集合称为边集 $E$，记作 $G=(V,E)$。 阶：图 $G=(V,E)$ 的顶点个数 $\lvert V\rvert$ 称为图的**阶**。 无向图：若边 $e\in E$ 没有方向，则 $G$ 称为**无向图**。其中边记作 $e=(u,v)$，其中 $u$ 与 $v$ 表示通过 $e$ 相连的两个顶点，$u$ 与 $v$ 之间无序。 有向图：若边 $e\in E$ 有方向，则 $G$ 称为**有向图**。其中边记作 $e=u\rightarrow v$ 或 $e=(u,v)$，$u$ 与 $v$ 之间有序。（注意，无向边可视为 $e_1=u\rightarrow v$ 与 $e_2=v\rightarrow u$。） 重边：端点和方向（如果有）相同的边为**重边**。 自环：两端连接相同顶点的边称为**自环**。 有限图与无限图：在图 $G=(V,E)$ 中，若边数 $\lvert V\rvert$ 与顶点数 $\lvert E\rvert$ 都是有限的，则称图 $G$ 为**有限图**。反之，若 $\lvert V\rvert$ 或 $\lvert E\rvert$ 是无限的，则称 $G$ 为**无限图**。 简单图：若一个图 $G$ 无重边和自环，那么称 $G$ 为简单图。 ## 邻居 相邻：（无向图）称两个顶点 $u$ 与 $v$ **相邻**，当且仅当存在 $e=(u,v)$。 邻域：（无向图）点 $u$ 的**邻域**为所有与之相邻的顶点的集合，记作 $N(u)$。 邻边：（无向图）与 $u$ 相连的边 $(u,v)$ 称为 $u$ 的**邻边**。 出边与入边：（有向图）从 $u$ 出发的边 $u\rightarrow v$ 称为 $u$ 的**出边**，到达 $u$ 的边 $v\rightarrow u$ 称为 $u$ 的**入边**。 度：图 $G$ 中与顶点 $u$ 关联的边数（约定自环记两次）称为顶点 $u$ 的**度**，记作 $d_G(u)$，不会混淆时记作 $d(u)$。 出度与入度：在有向图中，从 $u$ 出发的边数称为 $u$ 的**出度**，记作 $d^+(u)$；到达 $u$ 的边数称为 $u$ 的**入度**，记作 $d^-(u)$。 ## 路径 途径：连接一串相邻结点的序列称为**途径**，用点序列 $v_{0..k}$ 和边序列 $e_{1..k}$ 描述，其中 $e_i = (v_{i - 1}, v_i)$。常写为 $v_0\rightarrow v_1\rightarrow\dots\rightarrow v_k$。 迹：不经过重复边的途径称为**迹**。 回路：$v_0=v_k$ 的迹称为**回路**。 路径：不经过重复点的迹称为**路径**，也称**简单路径**。不经过重复点比不经过重复边强，所以不经过重复点的途径也是路径。注意题目中的简单路径可能指迹。 环：除 $v_0 = v_k$ 外所有点互不相同的途径称为**环**，也称**圈**或**简单环**。 ## 连通性 连通：对于无向图的两点 $u, v$，若存在途径使得 $v_0=u$ 且 $v_k=v$，则称 $u,v$ **连通**。 弱连通：对于有向图的两点 $u, v$，若将有向边改为无向边后 $u, v$ 连通，则称 $u,v$ **弱连通**。 连通图：任意两点连通的无向图称为**连通图**。 弱连通图：任意两点弱连通的有向图称为**弱连通图**。 可达：对于有向图的两点 $u,v$，若存在途径使得 $v_0=u$ 且 $v_k=v$，则称 $u$ **可达** $v$，记作 $u\rightsquigarrow v$。 ## 特殊图 基图：将有向图的有向边替换为无向边得到的图称为该有向图的**基图**。 有向无环图：不含环的有向图称为**有向无环图**，简称 **DAG**。 完全图：任意不同的两点之间恰有一条边的无向简单图称为**完全图**。$n$ 阶完全图记作 $K_n$，其边数为 $\frac{1}{2}n(n-1)$。 树：不含环的无向连通图称为**树**，树上度为 $1$ 的点称为**叶子**。树是简单图，满足 $\lvert V\rvert=\lvert E\rvert + 1$。若干棵（包括一棵）树组成的连通块称为**森林**。 稀疏图 / 稠密图： $\lvert E\rvert$ 远小于 $\lvert V\rvert^2$ 的图称为**稀疏图**，$\lvert E\rvert$ 接近 $\lvert V\rvert^2$ 的图称为**稠密图**。用于讨论时间复杂度为 $O(\lvert E\rvert)$ 和 $O(\lvert V\rvert^2)$ 的算法。 ## 子图 子图：满足 $V'\subseteq V$ 且 $E'\subseteq E$ 的图 $G'=(V',E')$ 称为 $G=(V,E)$ 的**子图**，记作 $G'\subseteq G$。要求 $E'$ 所有边的两端均在 $V'$ 中。 导出子图：选择若干个点以及两端都在该点集的所有边构成的子图称为该图的 **导出子图**。导出子图的形态仅由选择的点集 $V'$ 决定，记作 $G[V']$。 生成子图：$\lvert V'\rvert = \lvert V\rvert$ 的子图称为**生成子图**。 极大子图（分量）：在子图满足某性质的前提下，子图 $G'$ 称为**极大**的，当且仅当不存在同样满足该性质的子图 $G''$ 且 $G'\subsetneq G''\subseteq G$。$G'$ 称为满足该性质的**分量**。例如，极大的连通的子图称为原图的连通分量，即连通块。 ## 免责声明 ~~图论的知识点实在是太多了~~，详见[图论I](https://www.luogu.com.cn/article/amxn9li0)与[图论II](https://www.luogu.com.cn/article/qaggtm3r)。 ~~然后你就会发现上面的定义很像，因为作者也从那里学的。~~ # 数论 ~~哇塞，终于写到数论了呢。~~ 😊 ## 整除 设 $a,b$ 为给定整数，若存在整数 $c$，使得 $a=bc$，则称 $b$ **整除** $a$，记作 $b\mid a$，并称 $b$ 是 $a$ 的一个约数（或称因子），而称 $a$ 是 $b$ 的一个倍数。若不存在整数 $c$，则称 $b$ 不整除 $a$，记作 $b \nmid a$。 由定义不难得出整除的几个简单性质： * $b\mid c$ 且 $c\mid a \Rightarrow b\mid a$。 * $b\mid a$ 且 $b\mid c \Rightarrow b\mid (a\pm c)$，更一般的，若 $a_1,a_2,\dots,a_n$ 都是 $b$ 的倍数，则 $b\mid (a_1+a_2+\dots+a_n)$。 * 若 $b\mid a$，那么 $a=0$ 或 $\lvert b\rvert \le \lvert a\rvert$。因此，$b\mid a$ 且 $a\mid b\Rightarrow \lvert a\rvert=\lvert b\rvert$。 * （带余除法）设 $a,b$ 为整数，$b>0$，则存在整数 $q,r$，其中 $0\le r<b$，使得 $$a=bq+r$$ * 若 $n$ 是一个正整数，则 $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\dots+xy^{n-2}+y^{n-1})$$ * 若 $n$ 是一个正奇数，则（在上式中用 $-y$ 代替 $y$） $$x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+\dots-xy^{n-2}+y^{n-1})$$ ## 最大共约数与最小公倍数 ### 最大公约数 设 $a,b$ 不全为零，同时整除 $a,b$ 的整数（如 $\pm 1$）称为它们的**公约数**。不难知，$a,b$ 的公约数只有有限多个，我们将其中最大的一个称为 $a,b$ 的**最大公约数**，用符号 $\gcd(a,b)$ 表示。显然，最大公约数是一个正整数。 当 $\gcd(a,b)=1$ 时，称 $a$ 与 $b$ 互素。同理，若 $\gcd(a,b,\dots,c)=1$，称 $a,b,\dots,c$ 互素（注意，并非是两两互素）。 一些性质： * $\gcd(a,b)=\gcd(\pm a,\pm b)$。 * $\gcd(a,b)=\gcd(b,a)$。 * $\gcd(a,b)=\gcd(a,b+ka)$，其中 $k$ 为任意整数。 * 裴蜀等式： 设 $a,b$ 为不全为零的整数，则存在整数 $x,y$，使得 $$ax+by=\gcd(x,y)$$ 且满足 $x,y$ 的等式有无穷多组。 由上不难推得以下结论： * 一个不定方程 $ax+by=d$ （其中 $a,b$ 为不全为零的整数）有整数解的充分必要条件为 $d$ 是 $\gcd(a,b)$ 的倍数或为零。 * 两个整数 $a,b$ 互素的充分必要条件为存在整数 $x,y$，使得 $ax+by=1$。 * 若 $m\mid a$ 且 $m\mid b$，则 $m\mid \gcd(a,b)$。 * 若 $m>0$，则 $\gcd(ma,mb)=m\gcd(a,b)$。 * 若 $d=\gcd(a,b)$，则 $gcd(\frac{a}{d},\frac{b}{d})=1$。 * 若 $\gcd(a,m)=1,\gcd(b,m)=1$，则 $\gcd(ab,m)=1$。由此可推出，若 $\gcd(a,b)=1$，那么对于任意正整数 $k,l$，有 $\gcd(a^k,b^l)=1$。 * 设 $b\mid ac$，若 $\gcd(b,c)=1$，那么有 $b\mid a$。 * 设正整数 $a,b$ 之积是一个整数的 $k$ 次幂（$k\ge 2$），若 $\gcd(a,b)=1$，那么 $a,b$ 都是整数的 $k$ 次幂。多个整数同理。 * 设 $a>1$，$m,n>0$，则 $\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1$。 ### 最小公约数 设 $a,b$ 为两个非零整数，一个同时为 $a,b$ 的倍数的数被称为 $a,b$ 的**公倍数**。显然公约数有无穷多个，定义最小的一个正数为 $a,b$ 的**最小公倍数**，记作 $\operatorname{lcm}(a,b)$。多个整数同理。 一些性质： * $a$ 与 $b$ 的公约数都是其最小公倍数的的倍数。 * $\gcd(a,b)\operatorname{lcm}(a,b)=\lvert ab\rvert$。（注意，在多于两个整数的情况下，类似结论不成立） * 若 $a,b,\dots,c$ 两两互素，则 $\operatorname{lcm}(a,b,\dots,c)=\vert ab\dots c\rvert$。可推出，若 $a\mid m,b\mid m,\dots,c\mid m$，且 $a,b,\dots,c$ 两两互素，则 $ab\dots c\mid m$。 ## 素数 正整数 $n$ 总有两个正约数 $1,n$，若 $n$ 有且仅有这两个约数，则称 $n$ 为**素数**（质数）。反之，则为合数。 常用 $p$ 表示素数。 一些结论（下面 $p$ 表示一个素数）： * 正整数必有素约数。 * $n$ 是一个整数，则 $p\mid n$ 或 $\gcd(p,m)=1$。 * $a,b$ 是整数，若 $p\mid ab$，则 $a,b$ 中必有至少一个被 $p$ 整除。 * 素数有无穷多个。 * （唯一分解定理） 设 $n$ 为一个正整数，则可被分解为有限个素数之积，即 $n$ 是可唯一地表示为 $$n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$$ 其中 $p_1,p_2,\dots,p_k$ 是互不相同的素数，$\alpha_1,\alpha_2,\dots,\alpha_k$ 为正整数，这被称为 $n$ 的标准分解。 * 有唯一分解定理易知 $n$ 的全部正约数为 $p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k}$（其中 $0\le \beta_i\le\alpha_i,i=1,2,\dots,k$）。 由此可知，设 $\tau(n)$ 为 $n$ 的正约数的个数，$\sigma(n)$ 为 $n$ 的正约数之和，则 $$\tau(n)=(\alpha_1+1)(\alpha_2+1)\dots(\alpha_k+1)$$ $$\sigma(n)=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}$$ * $n$ 为完全平方数的充分必要条件为 $\tau(n)$ 为奇数。 * 对任意正整数 $n$，记号 $p^\alpha \mid\mid n$ 表示 $p^\alpha\mid n$ 但 $p^{\alpha+1} \nmid n$，可知 $\alpha$ 即为 $n$ 的标准分解中的 $p$ 的幂数。 * $n$ 为一个正整数，$p^{\alpha_p}\mid\mid n!$，则（$\lfloor x\rfloor$ 表示比 $x$ 小的最大整数） $$\alpha_p=\sum\limits_{i=1}^\infty\lfloor\frac{n}{p^i}\rfloor$$ ## 同余 设 $n$ 是给定正整数，若正整数 $a,b$ 满足 $n\mid(a-b)$，则称 $a$ 和 $b$ 模 $n$ **同余**，记作 $a\equiv b\pmod{n}$，若 $n\nmid(a-b)$，则 $a$ 和 $b$ 模 $n$ 不同余，记作 $a\not\equiv b\pmod{n}$。 另一种理解方式为 $a$ 与 $b$ 模 $n$ 同余为 $a$ 与 $b$ 除以 $n$ 的余数相同。 根据上面这些，整数集合可以根据模 $n$ 来分类。若 $a$ 与 $b$ 模 $n$ 同余，则 $a,b$ 属于一类。将这样的类称为**同余类**。 由带余除法，任意整数必恰与 $0,1,\dots,n-1$ 中的一个模 $n$ 同余，而这 $n$ 个数彼此模 $n$ 不同余，因此模 $n$ 有 $n$ 个不同的同余类，即为 $$M_i=\{x|x\in\mathbb{Z},x\equiv i\pmod{n} \},i=0,1,\dots,n-1$$ 在 $n$ 个同余类中各任取一个数作为代表，这样的 $n$ 个数被称为模 $n$ 的**完全剩余系**，简称完系。 若 $i$ 与 $n$ 互素，则同余类 $M_i$ 中的所有数都与 $n$ 互素，这样的同余类称为模 $n$ 的**缩同余系**。将模 $n$ 的缩同余类个数（即小于 $n$ 的与 $n$ 互素的正整数个数）为 $\varphi(n)$，称为**欧拉函数**。在模 $n$ 的 $\varphi(n)$ 个缩同余系中个人取一个数作为代表，这样的几个数为模 $n$ 的一个**缩剩余系**，简称缩系。不超过 $n$ 且与 $n$ 互素的 $\varphi(n)$ 个正整数称为模 $n$ 的最小正缩系。 欧拉函数的一些性质： * 设 $m=m_1m_2$，则 * 若 $\gcd(m_1,m_2)\ne1$，则 $\varphi(m)=m_2\varphi(m_1)$，其中 $m_2\le m_1$。 * 若 $\gcd(m_1,m_2)=1$，则 $\varphi(m)=\varphi(m_1)\varphi(m_2)$。 * 若已知 $m$ 的标准分解为 $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$，则 $\varphi(m)$ 可表示为 $$\varphi(m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})$$ * 对于任意正整数 $m$，有 $$\sum\limits_{d\mid m}\varphi(d)=m$$ 一些性质： * $a\equiv a\pmod{n}$。 * $a\equiv b\pmod{n} \Rightarrow b\equiv a\pmod{n}$。 * $a\equiv b\pmod{n},b\equiv c\pmod{n} \Rightarrow a\equiv c\pmod{n}$。 * $a\equiv b\pmod{n},c\equiv d\pmod{n}\Rightarrow a\pm c\equiv b\pm d\pmod{n}$。 * $a\equiv b\pmod{n},c\equiv d\pmod{n}\Rightarrow ac\equiv bd\pmod{n}$。 * $ac\equiv bc\pmod{n}\Rightarrow a\equiv b\pmod{\frac{n}{\gcd(n,c)}}$。 * $a\equiv b\pmod{n},d\mid n \Rightarrow a\equiv b\pmod{d}$。 * $a\equiv b\pmod{n},d\ne0\Rightarrow da\equiv db\pmod{dn}$。 * $a\equiv b\pmod{n_i}(i=1,2,\dots,k) \Rightarrow a\equiv b\pmod{\operatorname{lcm}(n_1,n_2,\dots,n_k)}$ * 设 $\gcd(a,n)=1$，$b$ 是任意整数。 若 $c_1,c_2,\dots,c_n$ 是模 $n$ 的一个完系，则 $ac_1+b,ac_2+b,\dots,ac_n+b$ 也是模 $n$ 的一个完系。 若 $d_1,d_2,\dots,d_{\varphi(n)}$ 是模 $n$ 的一个缩系，则 $ad_1,ad_2,\dots,ad_{\varphi(n)}$ 也是模 $n$ 的一个缩系。 * 设 $\gcd(a,n)=1$。$b$ 是任意整数，则有整数 $x$，使得 $ax\equiv b\pmod{n}$，易知这样的 $x$ 构成一个模 $n$ 的同余类。 特别地，当 $b=1$ 时，这样的 $x$ 称为 $a$ 关于模 $n$ 的逆元，记作 $a^{-1} \pmod n$，它们构成模 $n$ 的一个同余类，从而有一个 $a^{-1}$ 满足 $1\le a^{-1} <n$。 ## 一些数论定理 ### 费马小定理 设 $p$ 是素数，$a$ 是与 $p$ 互素的任意整数，则 $$a^{p-1}\equiv1\pmod{p}$$ 还有个变异式：对于任意整数 $a$ 有 $a^p\equiv a\pmod{p}$。 使用归纳法不难证明。 显然可以用费马小定理来求一个正整数 $a$ 模 $p$ 的逆元，这里不再赘述。 ### 欧拉定理 设 $m$ 为正整数，$a$ 是与 $m$ 互素的任意整数，$\varphi(m)$ 为欧拉函数，则 $$a^{\varphi(m)}\equiv 1\pmod{m}$$ 证明：取 $d_1,d_2,\dots,d_{\varphi(m)}$ 为模 $m$ 的一个缩系，因 $\gcd(a,m)=1$，那么 $ad_1,ad_2,\dots,ad_{\varphi(m)}$ 也是模 $m$ 的一个缩系，两个缩系在模 $m$ 的意义下互为排列，故 $$d_1d_2\dots d_{\varphi(m)}\equiv a^{\varphi(m)}d_1d_2\dots d_{\varphi(m)}\pmod{m}$$ 由于 $\gcd(d_i,m)=1$，因此 $\gcd(d_1d_2\dots d_{\varphi(m)},m)=1$，因此由上式可得欧拉定理。 费马小定理其实是欧拉定理的特殊情况。 ### 中国剩余定理（CRT） 设 $m_1,m_2,\dots,m_k$ 是两两互素的正整数，$M=m_1m_2\dots m_k$，$M_i=\frac{M}{m_i}(i=1,2,\dots,k)$，$b_1,b_2,\dots,b_k$ 为任意整数，则同余组 $$x\equiv b_1\pmod{m_1},\dots,x\equiv b_k\pmod{m_k}$$ 有解 $x=kM+\sum\limits_{i=1}^kM_1^{-1}M_ib_i，k\in\mathbb{Z}$。 # 参考资料 * 《算法导论》 * 《初等数论》 * 小蓝本高中卷集合，图论，数论 * [《图论I》](https://www.luogu.com.cn/article/amxn9li0)与[《图论II》](https://www.luogu.com.cn/article/qaggtm3r)——@[Alex_Wei](https://www.luogu.com.cn/user/123294) # upd log 2025/12/27：开始着手。 2025/12/28：完成集合与图论部分。 2025/12/31：完成数论部分。 2026/01/01 00:00：上传！ 2026/01/10：修改了一些笔误。 # 后记 ~~好累~~，新一年，上岸！😊 任何问题和补充指出在评论区，积极更改！

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...