Part1. 逻辑、集合、映射与计数
1.1 命题
命题：可以判断对错的叙述，形如若 \(p\) 则 \(q\)。
真值：若命题为真则为真，命题为假则为假。
逆命题：若 \(q\) 则 \(p\).
否命题：若 \(\neg p\) 则 \(\neg q\).
逆否命题：若 \(\neg q\) 则 \(\neg p\).
原命题和逆否命题真值相同，否命题和逆命题真值相同。
1.1.1 充分、必要、充要条件
命题若 \(p\) 则 \(q\)。
其中 \(p\) 为 \(q\) 的充分条件，\(q\) 为 \(p\) 的必要条件，\(p \Leftrightarrow q\) 为充要条件，即充分必要条件的合称。
| 条件 | 命题关系 |
|---|---|
| \(p\) 是 \(q\) 的充分不必要条件 | \(p \Rightarrow q\) 且 \(q \nRightarrow p\) |
| \(p\) 是 \(q\) 的必要不充分条件 | \(p \nRightarrow q\) 且 \(q \Rightarrow p\) |
| \(p\) 是 \(q\) 的充要条件 | \(p \Leftrightarrow q\) |
| \(p\) 是 \(q\) 的既不充分也不必要条件 | \(p \nRightarrow q\) 且 \(q \nRightarrow p\) |
【注意】："若 \(p\) 则 \(q\)" 不能与 "\(p \Rightarrow q\)" 混为一谈。
1.1.2 全称量词和存在量词
全称量词：意义为”所有，任意，每一个“，记为 \(\forall\).
存在量词：意义为”存在一个，至少有一个，某些“，记为 \(\exists\).
全称命题：结构为”对于 \(M\) 中任意一个 \(x\)，有 \(p(x)\) 成立“，简记为 \(\forall x \in M, p(x)\).
存在命题：结构为”存在 \(M\) 中的一个 \(x_0\)，使 \(p(x_0)\) 成立“，简记为 \(\exists x_0 \in M, p(x_0)\).
1.1.3 充分、必要条件的集合意义
若 \(p\) 以集合 \(A\) 的形式出现，若 \(q\) 以集合 \(B\) 的形式出现，即 \(A=\{x|p(x)\},B=\{x|q(x)\}\)，则充分，必要条件可叙述为：
- 若 \(A\subseteq B\)，则 \(p\) 是 \(q\) 的充分条件；
- 若 \(A \supseteq B\)，则 \(p\) 是 \(q\) 的必要条件；
- 若 \(A = B\)，则 \(p\) 是 \(q\) 的充要条件；
- 若 \(A \subsetneqq B\)，则 \(p\) 是 \(q\) 的充分不必要条件；
- 若 \(A \supsetneqq B\)，则 \(p\) 是 \(q\) 的必要不充分条件；
- 若 \(A \nsubseteq B\) 且 \(A \nsupseteq B\)，则 \(p\) 是 \(q\) 的既不充分也不必要条件；
1.2 集合
集合元素的三个特征：确定性，互异性，无序性。
元素与集合的关系：属于与不属于，记为 \(\in\)，\(\notin\).
集合与集合的关系：包含与不包含，记为 \(\subseteq\)，\(\nsubseteq\).
集合 \(A\) 大小表示为 \(|A|\).
通常用 \(\{\}\) 来框定集合，\(()\) 来框定 \(N\) 元组。
1.2.1 集合关系
| 关系 | 自然语言 | 符号语言 |
|---|---|---|
| 子集 | 集合 \(A\) 中所有元素都在集合 \(B\) 中，即若 \(x\in A\)，则 \(x \in B\). | \(A \subseteq B\) |
| 真子集 | 集合 \(A\) 是集合 \(B\) 的子集，且集合 \(B\) 中至少有一个元素不在集合 \(A\) 中。 | \(A \subsetneqq B\) |
| 集合相等 | 集合 \(A\)，\(B\) 中的元素相同 | \(A = B\) |
1.2.2 集合的基本运算
集合的并集：\(A \cup B=\{x|x\in A \vee x\in B\}\).
集合的交集：\(A \cap B=\{x|x\in A \wedge x\in B\}\).
集合的补集：\(\complement_U A=\{x|x\in U \wedge x \notin A\}\).
三种集合运用的性质：
-
并集的性质：\(A \cup\varnothing=A\)；\(A \cup A=A\)；\(A\cup B=B \cup A\)；\(A\cup B=A\Leftrightarrow B \subseteq A\).
-
交集的性质：\(A \cap\varnothing=A\)；\(A \cap A=A\)；\(A\cap B=B \cap A\)；\(A\cap B=A\Leftrightarrow A \subseteq B\).
-
补集的性质：\(A \cup(\complement_UA)=U\)；\(A \cap(\complement_UA)=\varnothing\)；\(\complement_U(\complement_UA)=A\)；\(\complement_U(A\cap B)=(\complement_UA) \cup(\complement_UB)\)；\(\complement_U(A\cup B)=(\complement_UA)\cap(\complement_UB)\).
集合的运算律
\(A \cup(B\cap C)=(A\cup B)\cap(A\cup C)\).
\(A \cap(B\cup C)=(A\cap B)\cup(A\cap C)\).
\(\complement_U(A\cap B)=\complement_UA\cup\complement_UB\).
\(\complement_U(A\cup B)=\complement_UA\cap\complement_UB\).
1.2.3 常见的数集记法
| 集合 | 自然数集 | 正整数集 | 整数集 | 有理数集 | 实数集 |
|---|---|---|---|---|---|
| 符号 | \(\mathbb{N}\) | \(\mathbb{N^*}\) | \(\mathbb{Z}\) | \(\mathbb{Q}\) | \(\mathbb{R}\) |
【注意】\(\mathbb{N}\) 为自然数集，包含 \(0\)，\(\mathbb{N}^*\) 为正整数集，不包含 \(0\)。
1.3 映射
对于非空集合 \(A,B\)。按照某种确定的对应关系 \(f\)，使对于集合 \(A\) 中的任意一个元素 \(x\)，在集合 \(B\) 中都有唯一确定的元素 \(f(x)\) 与之对应。则对应关系 \(f:A\to B\) 为从集合 \(A\) 到集合 \(B\) 的一个映射。
-
映射的定义域，像集合
在映射 \(f:A\to B\) 中，\(x\) 的取值范围 \(A\) 叫做映射的定义域；与 \(x\) 的值对应相等的 \(f(x)\) 值叫做 \(x\) 在映射 \(f\) 下的像，集合 \(f(A)=\{f(x)|x\in A\}\) 叫做映射的像集合。像集合 \(f(x)\) 是集合 \(B\) 的子集。
-
若 \(f(A)=B\)，则映射 \(f\) 称为满射；若对于 \(A\) 中任意两个不同的元素 \(x_1 \not= x_2\)，均有 \(f(x_1) \not= f(x_2)\)，则映射 \(f\) 称为单射；如果映射 \(f\) 既是单射又是满射，则映射 \(f\) 称为 1-1 映射。（感性理解为二分图最大匹配后的结果即为 1-1 映射）。\(\exists f^{-1}:B\to A\)，使得 \(\forall x\in A\)，均有 \(f^{-1}(f(x))=x,\forall y=B\)，均有 \(f(f^{-1}(y))=y\).
1.4 组合数学与计数
记 \(A_n^m\) 表示从 \(n\) 个数中选出 \(m\) 个数排列的方案数。
推导：第一个位置有 \(n\) 个数可选，第二个位置有 \(n-1\) 个数可选 ，\(\dots\)，第 \(m\) 个位置有 \(n-m+1\) 个数可选。则方案数为：\(\prod\limits_{i=1}^{m}(n-i+1)\).
化简可得：
\[A_n^m=\frac{n!}{(n-m)!} \]记 \(C_n^m\) 表示从 \(n\) 个数中选出 \(m\) 个数的方案数。
推导：就是将 \(A_n^m\) 的顺序忽略，即 \(\frac{A_n^m}{m!}\).
化简可得：
\[C_n^m=\frac{n!}{m!(n-m)!} \]1.4.1 组合计数的相关性质：
-
\(C_n^k=C_n^{n-k}\)
证明：在杨辉三角中，以 \(\frac{n}{2}\) 为中轴呈对称态，设杨辉三角中第 \(n\) 行的元素组成的数列为 \(d_k\)，即 \(d_n=d_{n-k}\)；综上，\(C_n^k=C_n^{n-k}\)
-
\(C_n^0+C_n^1+C_n^2+\dots+C_n^n=2^n\)
证明：在杨辉三角中，第 \(n\) 行的元素和为 \(2^n\)
-
\(C_n^0+C_n^2+C_n^4+\dots=C_n^1+C_n^3+C_n^5+\dots\)
证明：3在杨辉三角中，以 \(\frac{n}{2}\) 为中轴呈对称态。当 \(n\) 为偶数时，左右元素一一对应（1-1映射等价）。当 \(n\) 为奇数时，左右元素可交错映射（比如 \(n=5\) 时，杨辉三角中第 \(5\) 行的元素数列为 \(1~4~6~4~1\)，等价映射为 \(f(1)=4\)，\(f(1)=4\)，\(f(6)=6\)。且无论 \(n\) 的值为多少，总是可以找到一个等价映射，使得其成立，证明略）。
-
\(C_n^k=C_{n-1}^k+C_{n-1}^{k-1}\)
证明：在杨辉三角中，第 \(n\) 行 \(k\) 列元素等于第 \(n-1\) 行 \(k\) 列元素加上第 \(n-1\) 行 \(k-1\) 列元素。
-
\(C_n^k=\frac{n}{k}C_{n-1}^{k-1}\)
证明：\(C_n^k=\frac{n!}{k!(n-k)!}=\frac{n}{k}·\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{n}{k}C_{n-1}^{k-1}\)
-
\(C_n^k=\frac{n-k+1}{k}C_{n}^{k-1}\)
证明：\(C_n^k=\frac{n!}{k!(n-k)!}=\frac{n-k+1}{k}·\frac{n!}{(k-1)!(n-k+1)!}=\frac{n-k+1}{k}C_{n}^{k-1}\)
1.4.2 容斥原理
有 \(n\) 个集合 \(A_i\)，要计算 \(|\bigcup_{i=1}^n A_i|\) 的值。
首先看一种 \(n=3\) 的特殊情况：有三个集合 \(A,B,C\)。要计算 \(|A\cup B\cup C|\)，显然：
\[|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C| \]将此规律拓展，便得到了通解：
\[|A_1\cup A_2 \cup \dots \cup A_n|= \sum\limits_{i=1}^{n}A_i-\sum\limits_{1\le i<j \le n}|A_i\cap A_j|+\sum\limits_{1\le i<j<k \le n}|A_i\cap A_j\cap A_k|-\dots+(-1)^{n-1}|\bigcap_{i=1}^nA_i| \]证明：考虑计算贡献，左式每个元素出现一次，右式每个元素出现：\(C_k^1-C_k^2+C_k^3-\dots+(-1)^{i-1} ·C_k^i+\dots+(-1)^{k-1}·C_k^k=1\)
1.4.3 错位排列
对于长度为 \(n\) 的排列 \(A\)，求所有 \(A_i \not= i\) 的排列个数。
设 \(D_n\) 为长度为 \(n\) 的错位排列个数。
容易得到容斥：
\[D_n=n!-C_n^1·(n-1)!+C_n^2·(n-2)!+\dots+(-1)^nC_n^n \]化简得：
\[D_n=\sum\limits_{i=0}^{n}(-1)^iC_n^i·(n-i)!=n!\sum_{i=0}^{n}(-1)^i\frac{1}{i!} \]可以发现 sigma 里面一坨很像泰勒系数，利用一些高科技手段，证得 \(D_n\approx\frac{n!}{e}\).（我不会证啊，不过结论合乎周礼）。记得四舍五入。
Part2. 数列
2.1 数列基础
2.1.1 等差数列
对于一个数列 \(a\)，\(\forall i(1\le i<n),d\in \mathbb{R}\)，满足 \(a_{i+1}-a_i=d\)，则数列 \(a\) 为等差数列。
\(a_1\) 为等差数列的首项，\(a_n\) 为等差数列的末项，\(d\) 为公差。
性质
\(a_n=a_1+(n-1)·d=dn+(a_1-d)\)
\(S_n=\frac{(a_1+a_n)n}{2}=na_1+\frac{n(n-1)}{2}d\)
所以，等差数列的每一项都与第一项与公差有关。
2.1.2 等比数列
对于一个数列 \(a\)，\(\forall i(1\le i<n),q\in \mathbb{R}\) 且 \(q \not= 0\)，满足 \(\frac{a_{i+1}}{a_i}=q\)，则数列 \(a\) 为等比数列。
\(a_1\) 为等比数列的首项，\(a_n\) 为等比数列的末项，\(q\) 为公比。
性质
\(a_n=a_1·q^{n-1}=\frac{a_1(1-q^n)}{1-q}\)
等比数列的每一项都与第一项与公比有关。
2.1.3 求和符号的性质
- 重命名性质（任意更换下标字母不影响求和）；
- 累加性质，即 \(\sum\limits_{i=1}^{n}a_i=\sum\limits_{i=1}^{m}a_i+\sum\limits_{i=m+1}^{n}a_i(m<n)\)
- 线性性质，即 \(\sum a_i+b_i=\sum a_i+\sum b_i, \sum ka_i=k\sum a_i\)
- 交换顺序性质，即 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^m a_{ij}=\sum\limits_{j=1}^m \sum\limits_{i=1}^n a_{ij}\)
2.2 裂项
裂项的意义：在处理冗杂凌乱的分数数列时，可以考虑将其裂项之后，整理成简单的分式进行运算。
说白了就是一种工具。
例如：\(\sum\limits_{i=1}^n\frac{1}{i(i+1)}\)
\[\begin{aligned} &=\sum\limits_{i=1}^{n}\frac{1}{i}-\frac{1}{i+1}\\ &=\sum\limits_{i=1}^{n}\frac{1}{i}-\sum\limits_{i=1}^n\frac{1}{i+1}\\ &=\sum\limits_{i=1}^{n}\frac{1}{i}-\sum\limits_{i=2}^{n+1}\frac{1}{i}\\ &=1-\frac{1}{n+1} \end{aligned} \]这样就整理成了一个一阶的分式，和 \(n\) 阶的分式相比，减去了不少计算量。
2.2.1 Abel恒等式
令 \(S_n=\sum\limits_{i=1}^na_i\)，则
\[\sum\limits_{i=1}^na_ib_i=S_nb_n+\sum\limits_{i=1}^{n-1}S_i(b_i-b_{i+1}) \]2.3 递推转通项
若递推式形如 \(a_{n+1}=a_{n}+f(n)\)，可转为通项 \(a_{n+1}=a_1+\sum\limits_{i=1}^{n-1}f(i)\).
若递推式形如 \(a_{n+1}=a_{n}·f(n)\)，可转为通项 \(a_{n+1}=a_1\prod\limits_{i=1}^{n-1}f(i)\).
2.3.1 待定系数法
形式一
适用于解决形如 \(a_{n+1}=pa_n+q(p,q\in\mathbb{R})\) 形式的递推式转化。
待定系数为 \(p\) 的等比数列，即 \(a_{n+1}+x=p(a_n+x)\)，解得 \(x=\frac{q}{p-1}\)。
令 \(b_n=a_n+x\)，因为 \(b\) 是等比数列，所以 \(b_n=b_1·p^{n-1}\)
将 \(b\) 数列代回原式得 \(a_{n+1}+x=p(b_1·p^{n-1})\)
化简可得：\(a_{n+1}=(a_1+x)·p^{n}-x\)
将 \(x\) 代入上式得：\(a_{n+1}=(a_1+\frac{q}{p-1})·p^{n}-\frac{q}{p-1}\)
形式二
适用于解决形如 \(a_{n+2}=pa_{n+1}+qa_n(p,q\in\mathbb{R})\) 形式的递推式转化。
解除方程 \(x^2-px-q=0\) 的 \(x_1,x_2\).
若 \(x_1 \not= x_2\)，设 \(a_n=c_1x_1^n+c_2x_2^n\) 待定系数解出 \(c_1,c_2\)。
若 \(x_1=x_2\)，设 \(a_n=c_1x_1^n+c_2nx_1^n\) 待定系数解出 \(c1,c2\)。
带入可得通项公式。
2.3.2 换元法
适用于解决形如 \(a_{n+1}=pa_n+f(n)(p,f(n)\in\mathbb{R})\) 形式的递推式转化。
可以待定系数为 \(p\) 的等比数列，即 \(a_{n+1}+g(x+1)=p(a_n+g(n))\)，解出 \(g(n)\) 然后按照 2.3.1 的方法解即可。
还有另外一种做法，即将等式两边同时除以 \(p^{n+1}\)，转化为 \(\frac{a_{n+1}}{p^{n+1}}=\frac{a_{n}}{p^{n}}+\frac{f(n)}{p^{n+1}}\).
令 \(b_n=\frac{a_{n}}{p^{n}}\)，则原式为 \(b_{n+1}=b_n+\frac{f(n)}{p^{n+1}}\).
转化为：\(b_{n+1}=b_1+\sum\limits_{i=1}^{n-1}\frac{f(i)}{p^{i+1}}\).
然后将 \(b\) 转化为 \(a\) 数列即可。
Part3. 数学归纳法
3.1 第一数学归纳法
对于一个命题 \(f(n),n\in \mathbb{Z}^*\)，要证明其是否成立，则可以进行如下步骤：
- 证明 \(f(1)=1\)，即当 \(n=1\) 时，命题 \(f\) 成立；
- 若 \(f(k)=1\)，证明 \(f(k+1)=1\)，即假设当 \(n=k\) 时，命题 \(f\) 成立；则需证明当 \(n=k+1\) 时，命题 \(f\) 成立；
当这两个条件同时满足时，则条件（命题）成立，反之不成立。
例题1
求证 \(1+3+5+\dots+(2n-1)=n^2\)
证明：当 \(n=1\) 时，\(1 = 1^2\)，所以 \(f(1)=1\)；
假设 \(n=k\) 时，\(f(k)=1\)，则当 \(n=k+1\) 时，原式为 \(1+3+5+\dots+(2k-1)+[2(k+1)-1]\)
化简可得 \(1+3+5+\dots+(2k-1)+2k+1\)
将 \(1+3+5+\dots+(2k-1)=k^2\) 代入上式得：
\(k^2+2k+1=(k+1)^2\)
所以当 \(n=k+1\) 时，\(f(k+1)=1\).
即命题 \(f\) 成立。
例题2
求证：\(\sum\limits_{i=1}^n\left \lfloor \frac{i}{2} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor · \left \lfloor \frac{n+1}{2} \right \rfloor\)
证明：当 \(n=1\) 时，显然成立
假设 \(n=k\) 时，\(f(k)=1\)，则当 \(n=k+1\) 时，原式为 \(\sum\limits_{i=1}^{k+1}\left \lfloor \frac{i}{2} \right \rfloor = \left \lfloor \frac{k+1}{2} \right \rfloor · \left \lfloor \frac{k+2}{2} \right \rfloor\)
变形，代入得：
\[\left \lfloor \frac{k}{2} \right \rfloor · \left \lfloor \frac{k+1}{2} \right \rfloor + \left \lfloor \frac{k+1}{2} \right \rfloor = \left \lfloor \frac{k+1}{2} \right \rfloor ( \left \lfloor \frac{k}{2} \right \rfloor+1)=\left \lfloor \frac{k+1}{2} \right \rfloor + \left \lfloor \frac{k+2}{2} \right \rfloor \]所以当 \(n=k+1\) 时，\(f(k+1)=1\).
即命题 \(f\) 成立。
3.2 第二数学归纳法
对于一个命题 \(f(n),n\in \mathbb{Z}^*\)，要证明其是否成立，则可以进行如下步骤：
- 证明 \(f(1)=1\)，即当 \(n=1\) 时，命题 \(f\) 成立；
- 若 \(f(1,2,\dots,k)=1\)，证明 \(f(k+1)=1\)，即假设当 \(n=1,2,\dots,k\) 时，命题 \(f\) 成立；则需证明当 \(n=k+1\) 时，命题 \(f\) 成立；
当这两个条件同时满足时，则条件（命题）成立，反之不成立。
3.3 第三数学归纳法
对于一个命题 \(f(n),n\in \mathbb{Z}^*\)，要证明其是否成立，则可以进行如下步骤：
- 证明 \(f(2)=1\)，即当 \(n=2\) 时，命题 \(f\) 成立；
- 设递增数列 \(A\)，若 \(f(A_k)=1\)，证明 \(f(A_{k+1})=1\)，即当 \(n=A_{k+1}\) 时，命题 \(f\) 成立；
- 若 \(f(k)=1\)，证明 \(f(k-1)=1\)，即假设当 \(n=k\) 时，命题 \(f\) 成立；则需证明当 \(n=k-1\) 时，命题 \(f\) 成立；
当这三个条件同时满足时，则条件（命题）成立，反之不成立。
例题3
求证：对于任意正实数 \(x_1,x_2,\dots,x_n\)，均有 \(\frac{\sum\limits_{i=1}^{n}x_i}{n} \ge \sqrt[n]{x_1x_2\dots x_n}\)
证明：
当 \(n=2\) 时，原式成立，即 \(f(2)=1\).
当 \(n=2^k\) 时，两两一组合并，可得 \(f(2^{k})=1\).
假设 \(n=k\) 时，\(f(k)=1\)，则有：
\[\begin{array}{} \therefore n=k-1\\ \frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}=\frac{\sum\limits_{i=1}^{m-1} a_{i}+\frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}}{m}\ge\sqrt[m]{\sum\limits_{i=1}^{m-1} a_{i}+\frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}}=\left(\sum\limits_{i=1}^{m-1} a_{i}\right)^{\frac{1}{m}} \times\left(\frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}\right)^{\frac{1}{m}} \\ \therefore\left(\frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}\right)^{1}\ge\left(\sum\limits_{i=1}^{m-1} a_{i}\right)^{\frac{1}{m}} \times\left(\frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}\right)^{\frac{1}{m}} \\ \therefore\left(\frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}\right)^{\frac{m-1}{m}}\ge\left(\sum\limits_{i=1}^{m-1} a_{i}\right)^{\frac{1}{m}} \\ \therefore \frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}\ge\left(\sum\limits_{i=1}^{m-1} a_{i}\right)^{\frac{1}{m-1}} \\ \therefore \frac{\sum\limits_{i=1}^{m-1} a_{i}}{m-1}\ge\sqrt[m-1]{\left(\sum\limits_{i=1}^{m-1} a_{i}\right)} \end{array} \]故命题 \(f\) 成立。
Part4. 数论
4.1 整除
若 \(a\) 能整除 \(b\)，则 \(\exists n\in \mathbb{Z}\)，满足 \(an = b\)；记为 \(a | b\)
整除的性质
传递性：\(a|b,b|c\) 则 \(a|c\)；
可加减性：\(n|a,n|b\) 则 \(n|a\pm b\)
可乘性：\(a|b,c|d\) 则 \(ac|bd\)
4.2 最大公约数与最小公倍数
\(a,b\) 的最大公约数记为 \(\gcd(a,b)\)，\(\gcd(a,b)=\min\{x|(x|a)\wedge(x|b)\wedge(x>0)\}\)
\(a,b\) 的最小公倍数记为 \(\operatorname{lcm}(a,b)\)，\(\operatorname{lcm}(a,b)=\max\{x|(a|x)\wedge(b|x)\wedge(x>0)\}\)
带余除法
\(\forall a,b\in\mathbb{Z}^{+},\exists q,r\in\mathbb{Z}\)，使得：
\[\begin{cases} a=bq+r\\ 0\leq r \leq b-1 \end{cases} \]带余除法满足存在性和唯一性，证明略。
Part5. 常用定理及函数
5.1 欧拉函数
记 \(\varphi(n)\) 表示小于 \(n\) 的正整数中与 \(n\) 互质的数的个数。
计算方法：将总数减去与 \(n\) 不互质的数的个数。将 \(n\) 质因数分解后，记 \(p_1,p_2,p_3,\dots,p_k\) 为 \(n\) 的质因子，则有：
\[\varphi(n)=n-\sum\limits_{i=1}^{n}\frac{n}{p_i}+\sum\limits_{1\le i<j \le n}\frac{n}{p_ip_j}-\sum\limits_{1\le i<j<k \le n}\frac{n}{p_ip_jp_k}+\dots+(-1)^{k+1}\frac{n}{p_1p_2p_3\dots p_k} \]因数分解可得：
\[\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\dots(1-\frac{1}{p_k}) \]计算欧拉函数的步骤中运用到了容斥原理，可见容斥原理的应用范围非常广。
欧拉函数的性质：
-
若 \(\gcd(a,b)=1\)，则有 \(\varphi(a)·\varphi(b)=\varphi(ab)\)，即欧拉函数为积性函数。
证明：
设 \(A\) 为 \(a\) 的质因子集合，集合元素记为 \(p_1,p_2,p_3,\dots,p_k\)，\(B\) 为 \(b\) 的质因子集合，集合元素记为 \(P_1,P_2,P_3,\dots,P_m\)。
\(\because\gcd(a,b)=1\)，\(\therefore A \cap B=\varnothing\).
\(\because\varphi(a)=a(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\dots(1-\frac{1}{p_k}),\varphi(b)=b(1-\frac{1}{P_1})(1-\frac{1}{P_2})(1-\frac{1}{P_3})\dots(1-\frac{1}{P_m})\)
\(\therefore \varphi(ab)=ab(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\dots(1-\frac{1}{p_k})(1-\frac{1}{P_1})(1-\frac{1}{P_2})(1-\frac{1}{P_3})\dots(1-\frac{1}{P_m})\)
\(\therefore\varphi(a)·\varphi(b)=\varphi(ab)\)
-
若 \(p\) 为质数，\(\varphi(p)=p-1\).
证明：
\(\because p\) 为质数，\(\therefore\) 小于 \(p\) 的正整数中与 \(p\) 互质的数的个数为 \(p-1\).
-
若 \(p\) 为质数，\(\varphi(p)=p^k-p^{k-1}\).
证明：
\(\because p\) 为质数，\(\therefore\) 与 \(p\) 不互质的数只能为 \(p\) 的倍数，共有 \(p^{k-1}\) 个。
\(\therefore\) \(\varphi(p)=p^k-p^{k-1}\).
5.2 卡特兰数
记 \(C_n\) 为变量为 \(n\) 的卡特兰数值。其递推式为：
\[C_n=\sum\limits_{i=1}^{n-1}C_iC_{n-i} \]通项公式为：
\[C_n=\binom{2n}{n}-\binom{2n}{n−1}=\frac{\binom{2n}{n}}{n+1} \]卡特兰数通常可以解决一下问题（是一下问题的解）：
- 有 \(n\) 对括号匹配的序列数，解为 \(C_n\)；
- \(A,B\) 双方打羽毛球，从 \(0:0\) 打到 \(n:n\)，\(A\) 从来没有落后过的方案数，解为 \(C_n\)；
- 在一个 \(n\times n\) 的网格中，从 \((0,0)\) 处开始走，每次可以向上走一格或向右走一格，在任意时刻，向右走的次数不能少于向上走的的次数，求合法路径数，解为 \(C_n\)；
- 一个圆周上有 \(2n\) 个点，两两配对并在两点间连一条弦，要求所连的 \(n\) 条弦没有交点，求配对数，解为 \(C_n\)；
- 将 \(n\) 边的凸多边形以不相交的对角线分成 \(n−2\) 个三角形的方案数，解为 \(C_{n-2}\)。并可以转化为问题 \(4\)；
- \(\sum\limits_{i=1}^{2n} a_i(a_i\in\{-1,1\})=0,\forall 1\le k\le 2n,\sum\limits_{i=1}^k a_i\ge 0\) 的方案数，解为 \(C_n\)；（此问题为问题 \(2,3\) 的母题）；
卡特兰数的应用不止这些，遇到新问题应随机应变，转化为卡特兰数解。
5.3
Part6. 博弈论
对于一个无运气成分，无平局的游戏一定有必胜策略。
必败点：走到该点，采取最优策略一定失败；
制胜点：走到该点，采取最优策略一定胜利；
必胜策略推导：
- 只能走到只制胜点的都是必败点；
- 可以走到必败点的都是制胜点；