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

Matrix_J · 2026-01-01 00:00:07 · 算法·理论

前言

上一章：点这里

~~哇塞，作者可真是一只大鸽子，鸽了一个月。~~ 😔

不难注意到上篇是考试后发的，那么~~这篇也是~~。😮

本章将讲述集合等离散数学内容。😊

不涉及代码问题，只讲述基础数学内容。

集合

集合的概念

集合是由不同对象聚集而成的一个整体，称其中的对象为成员或元素。若一个对象 s 是集合 S 中的一个成员，则可以写作 s\in S，反之可以写作 s\notin S。

集合中不能出现多个相同的元素，且集合是无序的。当两个集合 A 和 B 包含相同的元素时，称集合 A 与 B 是相等的，写作 A=B。

我们采用下列特殊的符号来表示常见的集合

对一个具体的集合而言，可以用列举法或描述法给出它的准确而清晰的表示。

列举法

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

描述法

基于以下的概括原则：

对任给的性质 P，存在一个集合 S，它的元素恰好是具有性质 P 的所有对象，即
S=\{x \big| P(x)\}
其中 P(x) 表示 “x 具有性质 P”。

集合元素个数为有限数的集合为有限集，个数为无穷数的集合为无限集。如果有限集 A 的元素个数为 n，则称 A 为 n 元集，记作 \lvert A\rvert=n。

集合与集合之间的关系

在两个集合的关系中，子集是一个非常重要的概念。下面给出概念：

子集：A\subseteq B \Leftrightarrow 对任意 x\in A，都有 x\in B。
真子集：A \subsetneqq B \Leftrightarrow A\subseteq B 且存在 x'\in B，但 x'\notin A。
集合相等：A=B \Leftrightarrow A\subseteq B，且 B\subseteq A。（与上面的集合相等相同）

易知两个集合之间的关系的如下性质：

集合之间的运算

集合的交集、并集、补集是通过元素与几何的关系来定义的：

交集：C=A \cap B，其中 C 中的任意一个元素 x 满足 x\in A 且 x\in B。
并集：C=A \cup B，其中 C 中的任意一个元素 x 满足 x\in A 或 x\in B。
差集：C=A-B，其中 C 中的任意一个元素 x 满足 x\in A 且 x\notin B。
补集：给定一个集合 U，称 U 为全集，且 A\subseteq U，则定义集合 A 的补集为 \overline{A}=U-A。其中的元素 x 满足 x\in U 且 x\notin A。

记 U 为全集，容易证明集合的运算满足一下法则：

等幂律：A\cap A=A,A\cup A=A。
同一律：A\cap U=A,A\cup U=U,A\cap \varnothing=\varnothing,A\cup\varnothing=A。
互补律：A\cap\overline{A}=\varnothing,A\cup\overline{A}=U。
交换律：A\cap B=B\cap A,A\cup B=B\cup A。
结合律：A\cap(B\cap C)=(A\cap B)\cap C,A\cup(B\cup C)=(A\cup B)\cup 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\cup (A\cap B)=A,A\cap(A\cup B)=A。
反演律（摩根律）：\overline{A\cap B}=\overline{A}\cup\overline{B},\overline{A\cup B}=\overline{A}\cap\overline{B}。

容斥原理

容斥原理：

\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=2 时，设 A_1\cap A_2=B，A_1'=A_1-B，A_2'=A_2-B，则

A_1\cup A_2=A_1'\cup A_2'\cup B

同时，有 \big| A_1'\big|=\big| A_1\big|-\big| B\big|，\big| A_2'\big|=\big| A_2\big|-\big| B\big|，故

\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=2 时结论成立。

若当 n=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，改写容斥原理，得到下面的逐步淘汰原理：

\\ &= \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与图论II。

~~然后你就会发现上面的定义很像，因为作者也从那里学的。~~

数论

~~哇塞，终于写到数论了呢。~~ 😊

整除

设 a,b 为给定整数，若存在整数 c，使得 a=bc，则称 b 整除 a，记作 b\mid a，并称 b 是 a 的一个约数（或称因子），而称 a 是 b 的一个倍数。若不存在整数 c，则称 b 不整除 a，记作 b \nmid a。

由定义不难得出整除的几个简单性质：

若 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 互素（注意，并非是两两互素）。

一些性质：

裴蜀等式：

设 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,\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 为一个正整数，则可被分解为有限个素数之积，即 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，记号 p^\alpha \mid\mid n 表示 p^\alpha\mid n 但 p^{\alpha+1} \nmid n，可知 \alpha 即为 n 的标准分解中的 p 的幂数。
$$\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 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》与《图论II》——@Alex_Wei

upd log

2025/12/27：开始着手。

2025/12/28：完成集合与图论部分。

2025/12/31：完成数论部分。

2026/01/01 00:00：上传！

2026/01/10：修改了一些笔误。

后记

好累，新一年，上岸！😊

任何问题和补充指出在评论区，积极更改！