整除与因数倍数的定义： 设 a,b \in \mathbb{Z}，b \ne 0，若存在 q \in \mathbb Z，使得 a = bq，则称 b整除a， 记为 b \mid a，此时称 a 为 b 的因数，b 为 a 的倍数.
带余除法与余数的定义： 设 a,b \in \mathbb{Z}，b \ne 0，存在唯一的 q,r \in \mathbb Z，使得 a = bq + r,0 \leqslant r < |b| ，此时记 r 为余数，记为 \langle a \rangle _{b}（无歧义 b 可省略） 或 a \bmod b.
素数与合数的定义： 设 p \in \mathbb Z, \ p > 1. 如果 p 正因数只有 1 和 p，那么就称 p 为素数；反之则称 p 为合数.
001.1B 整除的性质
设 a,b,c \in \mathbb Z ，则
若 c \mid b,\ b \mid a，则 c \mid a.
若 b \mid a,\ c \ne 0，则 bc \mid ac.
若 c \mid a,\ c \mid b，对于任意 m，n \in \mathbb Z，都有 c \mid ma + nb.
若 b \mid a,\ a \mid b，则 a = \pm b.
证明方法：将 a,b,c 替换成 q.
001.1C 余数的性质
设 a_1, a_2, b \in \mathbb Z，则 (角括号外省略了 b )
证明方法：将 a_1, a_2 ,b 替换成 q.
001.2_ 欧几里得算法
[定理1.2.1（欧几里得定理）] 设 a, b, c 是不全为零的整数，若存在 q \in Z， 使得 a = bq + c， 则 (a, b) = (b, c)，即 (a + bq, b) = (a,b).
证明： 由 (b, c) \mid b, \ (b, c) \mid c 可得 (b, c) \mid bq + c 即 (b,c) \mid a，即 (b, c) 为 a, b 的公因数，可知 (b, c) \leqslant (a, b)， 同理由 (a, b) \mid a, \ (a, b) \mid b 得到 (a, b) \mid a - bq 即 (a,b) \mid c，可以得出 (a, b) 是 b,c 的公因数，即有 (a, b) \leqslant (b, c)，从而有 (a, b) = (b, c). \Box
001.2A 欧几里得算法
欧几里得算法又名辗转相除法，用来求解两数的最大公因数
设整数 a > 0, b > 0. 令 r_0 = a, r_1 = b，进行带余除法得到:
特别地，若 d = 1，代入得到所有解都可表示为 x = x_0 + bt, \ y = y_0 + at.
证明：
如果上述方程有整数解，显然有 (a, b) \mid c，即 d \mid c. 同时，由 *定理1.3.1* 可知，存在 s, t \in \mathbb Z，使得 sa + tb = (a, b)， 设 c = k(a, b), \ k \in \mathbb Z，则有 ska+tkb = k(a, b) = c，此时，方程必有两解：sk 与 tk.
设 x, y 是方程的任意一组解，有 ax + by = c，由 x_0, y_0 是方程的一组解，可得 ax_0 + by_0 = c，两式相减，得：
数据范围要求：若以 Exgcd(a, b) 为格式输入，则输入a和b不应当大于 10^{10^6}. 总之大可放心用.
#define ll long long
ll Exgcd(ll a, ll b, ll& x, ll& y)
{
if(b == 0){
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - (a / b) * y;
return d;
}
相当多情况下需要将一个整数 n 分解成标准分解式的形式，以解决问题；其他的情况只需要得到所有 n 的素因数，也可应用分解素因数的方法.
方法：对 n 分解素因数，那么顺序枚举 2 到 \sqrt n 的数. 如果这个数 i 能整除 n，则将它加入素因数表，并使 n 不停除以 i 直到不能整除，记录次数并记入指数表.
证明：首先 2 和 3 都是素数. 首先，如果 i 是合数，那么它的质因数应当小于它，由于是顺序枚举，那么 i 的所有质因数已被枚举过，枚举过程它的质因数的过程中 n 已将 i 的所有质因数除尽，从而 i 不可能整除 n，以此类推，在素因数表中的皆为素数. 由于各个素数互质，故而 n 的所有素因数都能加入素因数表.
时间复杂度：该方法只需要枚举 2 至 \sqrt n 的数据，复杂度为 \rm O(\sqrt n).
#define ll long long //不开 long long 见祖宗
#define MAXN 1e5 + 10 //可调整
#define MAXP 1e4 + 10 //可调整
ll vis[MAXN], prime[MAXP], n, p = 0;
//n即为素数筛中的n, p是过程中素数的下标, 最后p就是小于n的素数的数量
void EratosthenesPrime(ll N)
{
vis[1] = 1;
for (ll i = 2; i * i <= N; i++)
for (ll j = i, k = i * j; k <= n; j++, k = i * j)
vis[k] = 1; //由于i的1到i - 1倍都遍历过了，所以跳过
for (ll i = 1; i <= N; i++)
if (!vis[i]) prime[++p] = i;
}
#define ll long long //不开 long long 见祖宗
#define MAXN 1e5 + 10 //可调整
#define MAXP 1e4 + 10 //可调整
ll vis[MAXN], prime[MAXP], N, p = 0;
//n即为素数筛中的n, p是过程中素数的下标, 最后p就是小于n的素数的数量
void EulerPrime(ll N )
{
for (ll i = 2; i <= N; i++){
if (!vis[i]) prime[++p] = i;
for (ll j = 1; j <= p && i * prime[j] <= N; j++){
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
002_ 同余
002.1_ 同余基础
002.1A 同余的定义
设 a, b \in \mathbb Z，m 是一个正整数，如果用 m 分别去除 a， b，所得的余数相同，则称 a 和 b 关于模 m 同余，用符号 a \equiv b \pmod m 表示；如果余数不同，那么称 a 和 b 关于模 m 不同余，用符号 a \not\equiv b \pmod m 表示.
C++中的负数取余：如果运算过程中需要负数 n 需要对 m 取余，那么应当写为
ll MOD(ll n, ll m)
{
return (n % m + m) % m;
}
[同余的充要条件] 如果 a \equiv b \pmod m，替换成带余除法的形式，较为简单得：存在 t \in \mathbb Z，使得 a - mt = b 即 a - b = mt，从而 m \mid a - b. 故而我们得到 a \equiv b \pmod m 的充要条件是 m \mid a - b.
我们易于得到：
a \equiv a \pmod m
a \equiv b \pmod m \Longrightarrow b \equiv a \pmod m
a \equiv b \pmod m, \ b \equiv c \pmod m \Longrightarrow a \equiv c \pmod m
002.1B 同余的算术性质
[定理2.1.1] 设 a, b, c, d \in \mathbb Z，m 是任意正整数.
如果 a \equiv b \pmod m，那么 ac \equiv bc \pmod m.
如果 a \equiv b \pmod m, \ c \equiv d \pmod m，那么 a + c \equiv b + d \pmod m.
如果 a \equiv b \pmod m, \ c \equiv d \pmod m，那么 ac \equiv bd \pmod m. (注意这里只有充分性，没有必要性)
如果 a \equiv b \pmod m，那么对于任意正整数 n，有 a^n \equiv b^n \pmod m.
我们从同余的上述基本算术基本定理容易得到
如果 a \equiv b \pmod m，那么对于任意整系数多项式 f(x) = r_kx^k + \cdots + r_1x + r_0, \ r_i \in \mathbb Z, \ 0 \leqslant i \leqslant k，有 f(a) = f(b).
证明：
如果 a \equiv b \pmod m，则有 m \mid a - b，从而有 m \mid ac - bc，所以 ac \equiv bc \pmod m.
由 a \equiv b \pmod m, \ c \equiv d \pmod m 可知 m \mid a - b, \ m \mid c - d，所以有 m \mid (a - b) + (c - d) 即 m \mid (a + c) - (b + d)，可以推出 a + c \equiv b + d \pmod m.
由题设可知 m \mid a - b, \ m \mid c - d，则 m \mid c(a - b) + b(c - d)，即 m \mid ac + bd，从而有 ac \equiv bd \pmod m.
当 n 为 1 时，结论显然成立. 假设结论对 k (\geqslant 1) 也成立，即 a^k \equiv b^k \pmod m. 则当 n = k + 1 时，又因为 a \equiv b \pmod m，由 3 可知 aa^k \equiv bb^k \pmod m，即 a^{k + 1} \equiv b^{k + 1} \pmod m，从而根据数学归纳法，对于任意正整数 n，都有 a^n \equiv b^n \pmod m. \Box
[定理2.1.2] 设 a, b, c, d \in \mathbb Z，m 是任意正整数.
如果 a \equiv b \pmod m，正整数 d \mid m，那么 a \equiv b \pmod d.
如果 ac \equiv bc \pmod m，则 a \equiv b \pmod{\dfrac{m}{(c,m)}}. 特别地，如果 (c, m) = 1，则 a \equiv b \pmod m.
证明:
令 d = (c, m), 由 ac \equiv bc \pmod m 知，存在 k \in \mathbb Z，使得 ac - bc = km，于是有 (a - c)\dfrac{c}{d} = k\dfrac{m}{d} 即 \dfrac{m}{d} \mid (a - b)\dfrac{c}{d}. 又因为 d = (c, m)，所以 \left(\dfrac{c}{d}, \dfrac{m}{d}\right) = 1，从而有 \dfrac{m}{d} \mid a - b，即证得 a \equiv b \pmod{\dfrac{m}{d}}. \Box
我们对于模 m 的定理还有两个，有助于解决涉及模 m 的运算问题.
[定理2.1.3]
如果 a \equiv b \pmod m，又 a \equiv b \pmod n，那么 a \equiv b \pmod{[m, n]}.
如果 (m, n) = 1，那么
a \equiv b \pmod m \\
a \equiv b \pmod n
\end{cases}
\Longleftrightarrow a \equiv b \pmod{mn}
证明：
由 a \equiv b \pmod m，a \equiv b \pmod n，可得 m \mid a - b, \ n \mid a - b，可知 a, b 是 m, n 的公倍数，从而有 [m, n] \mid a - b 即 a \equiv b \pmod{[m, n]}.
由于 (m, n) = 1，所以我们有 [m, n] = mn，由1，该定理的充分性可证；显然有 m \mid mn, \ n \mid mn，从而必要性也可证得. \Box
002.2_ 剩余系
002.2A 完全剩余系和既约剩余系
我们可以发现，\mathbb Z 中的元素关于模 m 总共有 m 种余数的情况. 换言之，我们可将 \mathbb Z 中的元素分成 m 个集合，每个集合中的元素都关于模 m 同余. 我们将划分出的这些集合叫做等价类.
较为简单地，我们只需要从上述 m 个集合中选取 1 个元素讨论，我们便选取 m 个元素，使其构成一个集合 S，使得 \mathbb Z 中的每个元素都与且仅与 S 中的一个元素同余. 这便引出了剩余系的定义：
剩余系的定义: 设 S \subseteq \mathbb Z，如果任意整数都与 S 中的正好一个元素关于模 m 同余，则称 S 是模 m 的一个完全剩余系（简称剩余系），如果 S = \{ 0, 1, 2, \cdots, m - 1\} 则称 S 是关于模 m 的标准剩余系或最小非负剩余系.
[定理2.2.1] 设 S = \{ a_1, a_2, \cdots, a_k \} \subseteq \mathbb Z，则 S 是模 m 的一个完全剩余系的充要条件是： k = m, \ a_i \not\equiv a_j \pmod m (i \ne j).
这个定理根据定义易于理解，在此不做证明.
[定理2.2.2] 设 S = \{ a_1, a_2, \cdots, a_m \} 是模 m 的一个完全剩余系，(k, m) = 1，则 S' = \{ ka_1 + b, ka_2 + b, \cdots, ka_m + b \} 也是模 m 的一个完全剩余系.
证明： 不妨假设 ka_i + b \equiv ka_j + b \pmod m (i \ne j)，则由*定理2.1.1(2)*有 ka_i \equiv ka_j \pmod m，又因为 (k, m) = 10，由*定理2.1.2(2)*可知 a_i \equiv a_j \pmod m，但根据*定理2.2.1*，这与 S 是模 m 的一个完全剩余系相矛盾，继而 ka_i + b \not\equiv ka_j + b \pmod m (i \ne j)，即 S' 也是模 m 的完全剩余系. \Box
既约剩余系的定义： 在模 m 的一个完全剩余系 S 中，有的数与 m 互素，与 m 互素的数构成的集合称作模 m 的一个既约剩余系.
我们设对于模 m 所划分出的等价类中的一个为 S_{[r]} = \{ \cdots,r -m, r, r + m, r + 2m \cdots \}，则如果 (r, m) = 1 的话，根据 定理1.2.1 我们得到 (r - m, m) = (r + m, m) = (r, m) = 1，以此类推，该等价类中的所有元素都与 m 互素；反之，若 (r, m) \ne 1，同理该等价类中的所有元素都与 m 不互素. 由于模 m 的完全剩余系中的元素是从各个等价类中选取一个组成的，故而完全剩余系中与 m 互素的的个数根据等价类是固定的. 即既约剩余系的大小固定.
欧拉函数的定义： 据此，我们定义欧拉函数\varphi(m)，表示模 m 的既约剩余系的大小. 若考虑模 m 的一个标准剩余系，则 \varphi (m) 表示不大于 m 的正整数中与 m 互素的数的个数.
显然，一个素数与所有小于它的正整数互素，设 p 为一个素数，则有 \varphi(p) = p - 1. 从而对于任意正整数 m，都有 \varphi(m) \leqslant m - 1.
[定理2.2.3] 设 S = \{ a_1, a_2, \cdots, a_k\} \subseteq \mathbb Z，则 S 是 m 的一个既约剩余系的充要条件是：
当 i \ne j 时， a_i \not \equiv a_j \pmod m；
对任意 a_i \in S，都有 (a_i, m) = 1.
即：任意 \varphi(m) 个与 m 互素且两两关于模 m 不同余的数构成模 m 的一个既约剩余系.
这个定理通过定义易于证明，其实是我不想写了.
[定理2.2.4] 设 S = \{ a_1, a_2, \cdots, a_{\varphi(m)} \} 是模 m 的一个既约剩余系，(k, m) = 1，则 S' = \{ka_1, ka_2, \cdots, ka_{\varphi(m)} \} 也是模 m 的一个既约剩余系.
证明： 易证 ka_i \not \equiv ka_j \pmod m，而对于任意 ka_i \in S'，因 (k, m) = 1，就有 (ka_i, m) = (a_i, m) = 1，从而由*定理2.2.3*，定理得证. \Box
002.2B 欧拉定理、费马小定理、威尔逊定理
[定理2.2.5（欧拉定理）] 设 a \in \mathbb Z，m 是正整数，如果 (a, m) = 1 那么
\boxed{a^{\varphi(m)} \equiv 1 \pmod m} .
证明： 设 S = \{ a_1, a_2, \cdots, a_{\varphi(m)} \} 是模 m 的一个既约剩余系，则由定理2.2.4， S' = \{ aa_1, aa_2, \cdots, aa_{\varphi(m)} \} 也是模 m 的一个既约剩余系，所以 S' 中任一数必与 S 中某个数关于模 m 同余，且它们一一对应，从而在整体上看，根据定理2.1.1(3)，各个集合内的元素乘积同余，即：
由既约剩余系的定义可知，对所有 1 \leqslant i \leqslant \varphi(m)，都有 (a_i, m) = 1，所以 (\prod\limits_{i = 1}^{\varphi(m)}a_i,\ m) = 1，由上式得 m \mid a^{\varphi(m)} - 1，即 a^{\varphi(m)} \equiv 1 \pmod m. \Box
[定理2.2.6（费马小定理）] 如果 a \in \mathbb Z，p 为素数，则
\boxed{a^p \equiv a \pmod p}.
特别地，若 p \nmid a，则
\boxed{a^{p - 1} \equiv 1 \pmod p}.
证明： 若 p \nmid a，又因 p 为素数，则 (a, p) = 1，还有 \varphi(p) = p - 1，由欧拉定理，则易证 a^{p - 1} \equiv 1 \pmod p，同乘 a，则证有 a^p \equiv a \pmod p；若 p \mid a，则有 a^p \equiv a \equiv 0 \pmod p，此时定理显然成立. \Box.
002.2C 欧拉函数
002.3_ 乘法逆元
002.3A 线性同余方程
线性同余方程：对于 a, b, m \in \mathbb Z，m > 0 且 m \nmid a，则方程 ax \equiv b \pmod m 称为线性同余方程的一般形式. 如果有 ax_0 \equiv b \pmod m，则称 x \equiv x_0 \pmod m 是该同余方程的一个解.
我们根据 *同余的等价形式*，事实上， ax \equiv b \pmod m \Leftrightarrow m \mid ax - b，即存在 k \in \mathbb Z，使得 ax - mk = b，这里 k 的符号可以忽略，我们设 d = (a, m)，继而我们将该同余方程转换为了一个一次不定方程：
ax - mk = b
根据 *定理1.4.1*，该方程有解的充要条件是 d \mid b，设这个方程的一组解是 x_0, k_0 而且它的所有解都可表示为：
x = x_0 + \dfrac{m}{d}t, \ k = k_0 - \dfrac{a}{d}t
[定理2.3.1] 线性同余方程 ax \equiv b \pmod m，设 (a, m) = d，则同余方程有解的充要条件是 d | b，而且线性同余方程的解可表示为：
x \equiv x_0 + \dfrac{m}{d}t \pmod m, \quad t = 0, 1, \cdots, d - 1
证明：下面要证明该方程有 d 个解，且满足条件的 t = 0, 1, \cdots, d - 1. 事实上我们就是要从它的解的表示形式中筛出同余的各项. 不妨设 x_0 + \dfrac{m}{d}t_1 \equiv x_0 + \dfrac{m}{d}t_2 \pmod m，则根据 *定理2.1.1*可作如下变换：
x_0 + \dfrac{m}{d}t_1 \equiv x_0 + \dfrac{m}{d}t_2 \pmod m \Longleftrightarrow \dfrac{t_1 - t_2}{d}m \equiv 0 \pmod m \\ \Longleftrightarrow d \mid t_1 - t_2 \Longleftrightarrow t_1 \equiv t_2 \pmod d
#define ll long long //不开 long long 见祖宗
#define MAXN 1e5 + 10 //可调整
#define MAXP 1e4 + 10 //可调整
#define MAXF 1e5 + 10 //可调整
ll vis[MAXN], prime[MAXP], phi[MAXF], N, p = 0;
//n即为素数筛中的n, p是过程中素数的下标, phi[i]是i的欧拉函数
void EulerPhi(ll N)
{
for (ll i = 2; i <= N; i++){
if (!vis[i]) {
prime[++p] = i;
phi[i] = i - 1;
}
for (ll j = 1; j <= p && i * prime[j] <= N; j++){
vis[i * prime[j]] = 1;
if (i % phi[j])
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
002.4D 分解求欧拉函数及其代码
求单个数的素因数，直接在素因数分解的同时用 *定理2.2.1* 带入即可.
时间复杂度：时间复杂度显然与分解素因数相同，为 \rm O(\sqrt n).
数据范围要求：如果输入格式为SingleEuler(n)，那么n不应当大于 10^{15}.
#define ll long long // 不开long long见祖宗
ll N, ans;
// N是代求欧拉函数的变量，得到ans就是最后的结果
void SinglePhi(ll N)
{
ans = N;
for (int i = 2; i * i <= N; i++)
if (N % i == 0){
ans = ans / i * (i - 1); //公式中是 ans * (i - 1) / i，但先乘后除见祖宗（
while (N % i == 0) N /= i;
}
if (N > 1)
ans = ans / n * (n - 1);
}
002.5_ 同余方程
002.5A 中国剩余定理
我们定义一个线性同余方程组
\begin{cases}
x \equiv& a_1 \pmod{m_1} \\
x \equiv& a_2 \pmod{m_2} \\
&\vdots \\
x \equiv& a_k \pmod{m_k}
\end{cases}
其中， m_1, m_2, \cdots, m_k 两两互素，我们能够得到：
[定理2.5.1（中国剩余定理）] 定义 m = \prod {m_i}，\ M_i = m / m_i， \ N_i \equiv M_i^{-1} \pmod {m_i}，则上述方程存在唯一解：
long long getNi(long long p, long long q)
{
long long x = 0, y = 0;
exgcd(p, q, x, y);
return x * p;
}
long long CRT(int n, int ai[], int mi[])
long long ans = 0;
for(int i = 1; i <= n; i++) M *= mi[i];
for(int i = 1; i <= n; i++)
ans = ans + (ai[i] * getNi(M / mi[i], mi[i]) % M + M) % M;
return ans % M
}
考虑组合意义：D_{n-1} 是数字 2 位于第一位上，第二位不是 1 的错位排序的数目；D_{n-2} 是数字 2 位于第一位上，第二位是 1 的错位排序的数目。由于第一位上除了 1 一共 n - 1 种填法，所以在外面要乘上一个 n - 1。
003.2_ 偏序关系
003.2A 偏序的基本概念
由于序理论十分复杂，这里简要介绍几个基本概念。我们首先要形式化的表达出集合中的关系。
关系的定义： 设 X 为一个集合，X 上的关系是 X 上 有序对 的集合 X \times X的子集 R。我们把属于 R 的有序对 (a, b) 写作 a \preccurlyeq b （a 与 b 有关）；不属于 R 的有序对 (a,b) 写作 a \not \preccurlyeq b（a 与 b 无关）。
关系的可能的性质：
如果 \forall x \in X， x \preccurlyeq x，则称 \preccurlyeq 是 自反的。
如果 \forall x \in X， x \not \preccurlyeq x，则称 \preccurlyeq 是 反自反的。
如果 \forall x,y \in X， x \preccurlyeq y \Longrightarrow y \preccurlyeq x，则称 > \preccurlyeq 是 对称的。
如果 \forall x,y \in X 且 x \ne y 则 x \preccurlyeq y \Longrightarrow y \not > \preccurlyeq x，则称 \preccurlyeq 是 反对称的；等价地，若 x \preccurlyeq y 与 y > \preccurlyeq x 同时成立，则 x = y，则称 \preccurlyeq 是反对称的。
对于 \forall x,y,z \in X，如果 x \preccurlyeq y 且 y \preccurlyeq z，则x > \preccurlyeq z，则称 \preccurlyeq 是 对称的。
偏序的定义：如果集合 X 上的一个 偏序 是满足 自反、 反对称 和 传递 的一个关系。严格偏序 是 反自反的。此时我们称集合 X 为 偏序集， 记为 (X, \preccurlyeq)。当 X 是一个有限集时，称其为 有限偏序集。
我们可以得到，偏序集 (X, \preccurlyeq) 满足：
如果 \forall x,y \in X 且 x \ne y 则 x \preccurlyeq y \Longrightarrow y \not \preccurlyeq x；（反对称性）
若 x \preccurlyeq y 与 y \preccurlyeq x 同时成立，则 x = y；（反对称性）
对于 \forall x,y,z \in X，如果 x \preccurlyeq y 且 y \preccurlyeq z，则x \preccurlyeq z （传递性）
例如：(\mathbb{Z, \mid})（具有整除关系的整数集）是一个偏序集，这是因为对 \forall x , y, z\in \mathbb{Z}，x \mid x。x \mid y 且 y \mid x \Rightarrow x = y。x \mid y 且 y \mid z \Rightarrow x \mid z。
Hasse 图表示偏序关系： 有限偏序集都能表示为一个 DAG（有向无环图）。每一个元素都是一个点，如果满足 x \preccurlyeq y，就画一条 x 指向 y 的边。例：(\{1,2,3,4,5,6,7,8\}, \mid) 的偏序集可以表示为一张 DAG：
极大元和极小元： 对于一个元素 x \in X，如果不存在 y \in X，使 y \preccurlyeq x，则称 x 为偏序集 (X, \preccurlyeq) 上的一个 极小元；如果不存在 y \in X，使 x \preccurlyeq y 则称 x 为偏序集 (X, \preccurlyeq) 上的一个 极大元。
可比与不可比： 如果两个元素 x,y \in X 是可比的，当且仅当 x \preccurlyeq y 或 y \preccurlyeq x ；否则称其为不可比的. 如果集合 X 中的每一对元素都是可比的，则称这个集合 X 上的偏序 \preccurlyeq 是 全序。
线性拓展： 对于一个偏序集 (X,\preccurlyeq_1)，如果再在 X 上定义一个偏序关系 \preccurlyeq_2，使得对于 \forall a\preccurlyeq _1 b 都有 forall a \preccurlyeq _2 b，则称偏序集 (X, \preccurlyeq _2) 是偏序集 (X, \preccurlyeq _1) 的一个 拓展。通俗的说，偏序集的线性在原来的偏序集上能定义出一个不改变任意两元素原有拓扑关系。特别地，若这个拓展是线性有续集，则称他为 线性拓展。
[定理3.2.2] 有限偏序集总存在线性拓展。
证明： 将有限偏序集看为一个 DAG，则这个 DAG 上总能跑 拓扑排序，跑完拓扑排序得到的就是这个有限偏序集的线性拓展。
003.2B 偏序集上的链
链与反链定义：链 是 X 的一个子集，满足链上的元素两两可比。反链 满足两两不可比。事实上，如果用 Hasse 图表示的话，链能够表示为一根图上的链（这是由于偏序满足反对称性，所以不存在环，而两两元素之间总存在一条边），故链上的元素可以按照偏序关系排序。
易于有，如果 A 是一条链而 C 是一条反链： |A \cap C| \leqslant 1。
[定理3.2.3] 设 (X, \preccurlyeq) 为一个有限偏序集，并设 r 是最长的链，则 X 最少可以划分出 r 个反链。
以及上述定理的对偶定理：
[定理3.2.4（Dilworth定理）] 设 (X, \preccurlyeq) 为一个有限偏序集，并设 r 是最长的反链，则 X 最少可以划分出 r 个链。
003.3_ 莫比乌斯反演
003.3A 莫比乌斯反演的一般形式
This section includes more sophisticated mathematics than the other sections in this chapter.这一节所涉及的数学比前面所涉及都更加深奥和微妙。———— 《Introductory Combinatorics》Richar A. Brualdi
证明：我们假设对于 M,N \subseteq L 且 M \ne N，存在 s \in B_M 且 s \in B_N。
由于 M \ne N，则一定满足存在 A_i 使得 i \in M 且 i \not \in N （由于 M, N 是对称的，所以 i \in N 且 i \not \in M 的情况可以省略）。根据 B 的定义，由于 s \in B_M 所以 s \in A_i ；由于 s \in B_N 所以 s \in \overline{A_i}。
但是这是矛盾的。故假设不成立，不存在这样的 s，所以所有 B_J 是无交的。
引理 2 （上式的无交并与原等式右侧等价）：\bigcap \limits_{\substack{i\not \in L \\ \text{or } i = \varnothing}} A_i = \bigsqcup\limits_{J \subseteq L} B_J
long long Sum(long long n)
{
long long ans = 0;
long long l = 1, r;
while(l <= n){
r = n / (n / l);
ans += (f[r] - f[l - 1]) * (n / l); // 这里 f[i] 代表函数前缀和
l = r + 1;
}
return ans;
}
00X.2 群论相关概念
群：对于一个非空集合 G，和一个运算 \cdot，如果满足：
任意 a, b \in G，都有 a \cdot b \in G；
任意 a, b, c \in G，都有 a \cdot (b \cdot c) = (a \cdot b) \cdot c，即群的结合律；
存在 e \in G，使得对任意 a \in G，都有 a \cdot e = e \cdot a = a，并称 e 是群 G 的单位元；
对于任意 a \in G，存在 b \in G，使得 a \cdot b = b \cdot a = e，并称 b 是 a 的逆元，记为a^{-1}.
则称 (G,\cdot) 是一个群，表示该群和运算 a \cdot b 时，通常省略运算 \cdot，记为群 G 和 ab.
对于一个群 G 和 a \in G，我们一般将 \underbrace{aa \cdots a} 简记为 a^n.
群的阶：对于一个群 G，如果集合 G 的大小 |G| 是有限的，则称它为有限群，反之则称他为无限群. 对于有限群 G，|G| 称为群 G 的阶。
交换群：对于一个群 G，如果对于任意 a, b \in G，都有 ab = ba，则称这个群为 \text{Abel} 群 或 交换群. 通常交换群的运算用 + 表示，也将 a^n 记为 na.