逻辑1. 充分条件、必要条件与充要条件的概念

若 \(p\Rightarrow q\)，则 \(p\) 是 \(q\) 的充分条件，\(q\) 是 \(p\) 的必要条件。\(p\) 是 \(q\) 的充分不必要条件，\(p\Rightarrow q\) 且 \(q\not\Rightarrow p\)。\(p\) 是 \(q\) 的必要不充分条件，\(p\not\Rightarrow q\) 且 \(q\Rightarrow p\)。\(p\) 是 \(q\) 的充要条件，\(p\Leftrightarrow q\)。

2. 全称量词和存在量词

全称量词：\(\forall\)。存在量词：\(\exists\)。

(资料图片仅供参考)

集合1. 集合与元素

集合元素的三个特征：确定性、互异性、无序性。元素与集合的关系是属于或不属于关系，用符号 \(\in\) 或 \(\notin\) 表示。集合的表示法：列举法、描述法、图示法。自然数集：\(N\)，正整数集：\(N^*\) 或 \(N_+\)，整数集：\(Z\)，有理数集：\(Q\)，实数集：\(R\)。

2. 集合间的基本关系

子集：集合 \(A\) 中所有元素都在集合 \(B\) 中，\(A\subseteq B\)。真子集：集合 \(A\) 是 \(B\) 的子集，且集合 \(B\) 中至少有一个元素不在集合 \(A\) 中，\(A\subsetneq B\)。集合相等：集合 \(A\)，\(B\) 中元素相同，\(A=B\)。

3. 集合的基本运算

集合的并集：\(A\cup B={x|x\in A 或 x\in B}\)。集合的交集：\(A\cap B={x|x\in A 且 x\in B}\)。集合的补集：\(\complement_UA={x|x\in U 且 x\notin A}\)。结合律：对于任意三个集合 \(A\)，\(B\) 和 \(C\)，结合律指的是 \((A ∪ B) ∪ C = A ∪ (B ∪ C)\) 和 \((A ∩ B) ∩ C = A ∩ (B ∩ C)\)。交换律：对于任意两个集合 \(A\) 和 \(B\)，交换律指的是 \(A ∪ B = B ∪ A\) 和 \(A ∩ B = B ∩ A\)。对称差：\(A \Delta B = (A - B) ∪ (B - A)\)

计数（映射）1. 映射的概念

两集合 \(A\)，\(B\)：\(A\)，\(B\) 是两个非空集合。对应关系 \(f\)：\(A\rightarrow B\)，如果按照某种确定的对应关系 \(f\)，使对于集合 \(A\) 中的任意一个元素 \(x\)，在集合 \(B\) 中都有唯一确定的元素 \(f(x)\) 与之对应。名称：称 \(f\)：\(A\rightarrow B\) 为从集合 \(A\) 到 \(B\) 的一个映射。

2. 映射的有关概念

若 \(f(A)=B\)，则映射 \(f\) 称为满射；若对于 \(A\) 中任意两个不同的元素 \(x_1\not=x_2\)，均有 \(f(x_1)\not=f(x_2)\)，则映射 \(f\) 称为单射；如果映射 \(f\) 既是单射又是满射，则映射 \(f\) 称为一一映射。此时存在 \(f^{-1}\) ：\(B\rightarrow A\)，使得 \(\forall x\in A\)，均有 \(f^{-1}(f(x))=x\)，\(\forall y\in B\)，均有 \(f(f^{-1}(y))=y\)。

3. 映射的应用

\(C_n^k=\frac{n!}{k!(n-k)!}\)\(C_n^k=C_n^{n-k}\)\(C_n^0+C_n^1+C_n^2+\cdots +C_n^n=2^n\)\(C_n^0+C_n^2+C_n^4+\cdots +C_n^{2k}=C_n^1+C_n^3+C_n^5+\cdots+C_n^{2k+2}\)\(C_n^k=C_{n-1}^k+C_{n-1}^{k-1}\)\(C_n^k=\frac{n}{k}C_{n-1}^{k-1}\)\(C_n^k=\frac{n-k+1}{k}C_n^{k-1}\)

容斥

\(|\cup_{i=1}^{n}A_i|=\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}\times|\cap_{i=1}^{n}A_i|=\sum\limits_{k=1}^{n}(-1)^{k-1}\times \sum\limits_{1\le x_1\le x_2\cdots x_k\le n}|\cap_{i=1}^{k}A_{x_i}|\)

数列

等差数列：\(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\)等比数列：\(a_n=a_1q^{n-1}(q\not=0)\)，\(s_n=\frac{a_1(1-q^n)}{1-q}(q\not=1)\)，\(s_n=na_1(q=1)\)

裂项

\(\sum\limits_{i=1}^{n}i=\frac{1}{2}n(n+1)\)\(\sum\limits_{i=1}^{n}i^2=\frac{1}{6}n(n+1)(2n+1)\)\(\sum\limits_{i=1}^{n}i^3=\frac{1}{4}n^2(n+1)^2\)\(\sum\limits_{i=0}^{n}C_n^ia^ib^{n-i}=(a+b)^n\)

Abel恒等式

\(\sum\limits_{a_i}^{b_i}=S_nb_n+\sum\limits_{i}^{n-1}S_i(b_{i+1}-b_i)\)

数学归纳法1. 第一归纳法先证 \(n=1\) 时，成立若 \(n=k\) 时，成立再证 \(n=k+1\) 时，成立2. 第二归纳法先证 \(n=1\) 时，成立若 \(n=1, n=2, \cdots n=k\) 时，成立再证 \(n=k+1\) 时成立3. 第三归纳法（证明 \(n\) 元均值不等式）先证 \(n=2\) 时，成立若 \(n=2^k\) 时，成立再证 \(n=2^m\) 时，成立若 \(n = m\) 时，成立最后证 \(n=m-1\) 时，成立博弈论先求第一制胜点递推：\((1)\) 能走到制胜点的点都是必败点。\((2)\) 无论怎么走都是必败点，才是必胜点。根据递推的结果猜测策略用数学归纳法证明此策略汉诺塔

令 \(n\) 为当前汉诺塔的个数，且均在第一根柱子上。则先将上面 \(n-1\) 个，按顺序移动到第二根柱子上。再将第 \(n\) 个汉诺塔移动到第三根柱子上。最后将 \(n - 1\) 个汉诺塔，按顺序移动到第三根柱子上。于是递推公式即为：\(a_n=2a_{n-1}+1\)。转变为通项公式即为：\(a_n=2^n-1\)。

砝码问题

只有一边放置砝码，有 \(n\) 个砝码，则最多能够称出 \(2^n-1\) 种重量。两边都可以放置砝码，有 \(n\) 个砝码，则最多能够称出 \(\frac{3^n-1}{2}\) 种重量。

错排

\(n\) 元错排公式：\(D_n=\sum\limits_{i=0}^{n}(-1)^iC_n^i(n-i)!=\sum\limits_{i=0}^{n}(-1)^i\frac{n!}{i!}=n!\sum\limits_{i=0}^{n}(-1)^i\frac{1}{i!}\approx \frac{n!}{e}\)递推式：\(D_n=(n-1)(D_{n-1}+D_{n-2})\)

卡特兰数

递推式：\(H_n=\sum\limits_{i=0}^{n}H_iH_{n-i}\)通项公式：\(H_n=C_{2n}^{n}-C_{2n}^{n-1}=\frac{C_{2n}^{n}}{n+1}\)

递推公式向通项公式的转化1. 待定系数

递推式两边同时 \(+k\)，再利用第一项和等比数列公式求出通项公式。

\[ \begin{cases}a_1=1 \\[2ex]a_{n+1}=2a_n+1\end{cases}\]\[a_{n+1}+k=2(a_n+k)\]\[k=1\]

最终通项公式为：\(a_n=2^n-1\)

2. 两边同除以 \(p^{n+1}\)

递推式两边同时除以 \(p^{n+1}\)，再利用第一项和等差数列公式求出通项公式。

\[ \begin{cases}a_1=1 \\[2ex]a_{n+1}=2a_n+1\end{cases}\]\[\frac{a_{n+1}}{2^{n+1}}=\frac{a_n}{2^n}+\frac{1}{2^{n+1}}\]

最终通项公式为：\(a_n=2^n-1\)

3. 取倒数

递推式两边同时取倒数，再利用第一项和等比数列公式或等差数列公式求出通项公式。

4. fib

当有 \(n+1\) 项与 \(n\) 和 \(n-1\) 有关系时，将第 \(k\) 项转换为 \(x^{k}\)，再利用前两项求得系数。斐波那契通项公式：

\[\frac{\sqrt[]{5}}{5}((\frac{1+\sqrt[]{5}}{2})^n-(\frac{1-\sqrt[]{5}}{2})^n)\]Stirling 数

第一斯特林数：\(S(p, i)=S(p-1, i-1)+iS(p-1,i)\) \((1\le i\le p-1)\)第二斯特林数：\(S(p,i)=S(p-1, i-1)+(p-1)S(p-1, i)\)

Bell 数

\(B_p=\sum\limits_{i=0}^{p}S(p, i)\)\(B_p=\sum\limits_{i=0}^{p-1}C_{p-1}^{i}B_{p-i-1}\)

整除1. 定义

\(a|b:\exists n\in Z\) 使得 \(b=an\)。

2. 性质

传递性：\(a|b, b|c\Rightarrow a|c\)可加减性：\(n|a, n|b\Rightarrow n|a\pm b\)可乘性：\(a|b, c|d\Rightarrow ac|bd\) \((a|b\Rightarrow a|bd)\)

最大公因与最小公倍1. 定义

\(\gcd(a, b):\max(m\mid m|a 且 m|b)\)\(\operatorname{lcm}(a, b):\min(n\mid a|n 且 b|n, n\gt 0)\)

2. 带余除法

\(a\div b=q\cdots r\)确定了 \(a\) 和 \(b\)，那么 \(q\) 和 \(r\) 就确定了。

3. 辗转相除

\((1)\) \((a, b)=(a-b, b)\)\(\forall x\in\lbrace a, b的公因数\rbrace\)\(x|a, x|b\Rightarrow x|a-b\Rightarrow x\in\lbrace a-b与b的公因数\rbrace\)\(\therefore\lbrace a, b的公因数\rbrace =\lbrace a-b与b的公因数\rbrace\)\((2)\) 若 \(a\div b=q\cdots r\)，则 \((a, b)=(b, r)\)证明：通过 \((1)\) 多做几次就好了。\((3)\) 辗转相除法

\[\forall a\gt b, a_1=a, b_1=b, a_1\div b_1=q_1\cdots r_1\]\[(a_1, b_1)=(b_1, r_1)\]

令 $$a_2=b_1, b_2=r, a_2\div b_2=q_2\cdots r_2$$ $$(a_2, b_2)=(b_2, r_2)$$

\[\vdots\]

直到 $$r_n=0\ 时，(a_n, b_n)=b_n$$

4. 裴蜀定理

\(ax+by=(a, b)\)

5. \(\gcd\) 的性质

\((a, b, c)=((a, b), c)\)\((a, b)=(a, b, ax)\)\((a, b, c)=((a, b), (a, c))\)

6. \(\gcd\) 的重要式子

已知 \(a, b\) 为正整数，\((2^a-1, 2^b-1)=2^{(a, b)}-1\)已知 \(a, b\) 为正整数，\((2^{2^a}+1, 2^{2^b}+1)=1\)

算术基本定理1. 质数的定义

\(p\ge 2, n|p\Rightarrow n=1 \ 或 \ n=p\)

2. 分解质因数

一个大于 \(1\) 的正整数 \(n\) 可以分解为若干个质数的乘积，若不考虑质因子之间的顺序，这种分解方式是唯一的。

3. \(v_p(n)\)

\(v_p(n)\) 表示 \(n\) 的标准分解式中所含质因子 \(p\) 的指数。\(v_p(n_1n_2)=v_p(n_1)+v_p(n_2)\)\(v_p(\gcd(n_1, n_2))=\min(v_p(n_1), v_p(n_2))\)\(v_p(\operatorname{lcm}(n_1, n_2))=\max(v_p(n_1), v_p(n_2))\)

\[v_p(n_1, n_2)=\begin{cases}\min(v_p(n_1), v_p(n_2))\ (v_p(n_1)\not= v_p(n_2))\\[2ex]\ge v_p(n_1)=v_p(n_2)\ (v_p(n_1)=v_p(n_2))\end{cases}\]4. 因数个数与因数和

设正整数 \(n\) 的标准分解式为： \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\)因数个数公式：\(d(n)=(e_1+1)(e_2+1)\cdots (e_k+1)\)因数和公式：\(\sigma(n)=\frac{p_1^{e_1+1}-1}{p_1-1}\frac{p_2^{e_2+1}-1}{p_2-1}\cdots \frac{p_k^{e_k+1}-1}{p_k-1}\)因数积：\(n^\frac{d(n)}{2}\)

5. \(\gcd\) 的性质

\((ma, mb)=m(a, b)\)\((a, uv)=(a, (a, u)v)\)\((u, v)=1\Rightarrow (a, uv)=(a, u)(a, v)\)

6. \(mn\) 与 \(\gcd\) 和 \(\operatorname{lcm}\) 的关系

\((m, n)\times [m, n]=mn\)

同余1. 定义

\(n|a-b\Rightarrow a\equiv b\pmod n\)

2. 性质

若 \(a\equiv b\pmod n\)，则 \(a\) 与 \(b\) 对 \(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_1\equiv a_1\pmod n, b_1\equiv b_2\pmod n\Rightarrow a_1\pm b_1 \equiv a_2\pm b_2\pmod n\)可乘性：\(a_1\equiv a_1\pmod n, b_1\equiv b_2\pmod n\Rightarrow a_1\times b_1 \equiv a_2\times b_2\pmod n\)可除性：\(ka\equiv kb\pmod n\Rightarrow a\equiv b\pmod n\)互质可除性：\(ka\equiv kb\pmod n, (k, n)=1\Rightarrow a\equiv b\pmod n\)

3. 特殊数的余数特征

若 \(m|10^k\)，\(n=a\cdot 10^k+b\)（其中 \(b\) 为 \(n\) 的末 \(k\) 位数，则 \(n\equiv b\pmod m\)若 \(m|10^k-1\)，\(n=a_s\cdot 10^{sk} +a_{s-1}\cdot 10^{(s-1)k}+\cdots +a_1\cdot 10^k+a_0\)，其中 \(a_s, a_{s-1}, \cdots , a_0\) 均小于 \(10^k\)。则 \(n\equiv a_s+a_{s-1}+\cdots +a_0\pmod m\)若 \(m|10^k+1\)，\(n=a_s\cdot 10^{sk} +a_{s-1}\cdot 10^{(s-1)k}+\cdots +a_1\cdot 10^k+a_0\)，其中 \(a_s, a_{s-1}, \cdots , a_0\) 均小于 \(10^k\)。则 \(n\equiv a_0-a_1+a_2-a_3+\cdots +(-1)^s\cdot a_s\pmod m\)

经典余数定理1. 剩余类

\(Z\) 按\(\bmod n\) 分为 \(0\pmod n, 1\pmod n,\cdots n-1\pmod n\)\(Z_n=\lbrace\overline{0}, \overline{1},\cdots, \overline{n-1}\rbrace\)

2. 完全剩余系（简称完系）

\(x=\lbrace a_i\in\overline{i}\mid 0\le i\le n-1\rbrace\)

3. 欧拉 \(\varphi\) 函数

\(\varphi(n)\):\(0\sim n-1\) 与 \(n\) 互质的个数\(m, n\) 互质 \(\Rightarrow\varphi(mn)=\varphi(m)\cdot\varphi(n)\)

4. 欧拉 \(\varphi\) 函数的计算

\(\varphi(n)=n\cdot \prod\limits_{i=1}^k(1-\frac{1}{p_i})\)

5. 既约剩余系（简称完系）

既约剩余系中的元素是剩余类中与 \(n\) 互质的元素。

6. 同余逆

已知 \((a, n)=1\)，则存在整数 \(b\) 使得 \(ab\equiv 1\pmod n\)，且这样的 \(b\) 在模 \(n\) 意义下是唯一的。则 \(b\) 称为 \(a\) 模 \(n\) 的同余逆，通常记作 \(a^{-1}\pmod n\)

7. 性质

若 \(\lbrace a_1, a_2, \cdots, a_n\rbrace\) 为模 \(n\) 的完系，则 \(\lbrace a_1+k, a_2+k, \cdots, a_n+k\rbrace\) 也为模 \(n\) 的完系若 \(\lbrace a_1, a_2, \cdots, a_n\rbrace\) 为模 \(n\) 的完系，且 \((m, n)=1\)，则 \(\lbrace ma_1, ma_2, \cdots, ma_n\rbrace\) 也为模 \(n\) 的完系若 \(\lbrace a_1, a_2, \cdots, a_{\varphi(n)}\rbrace\) 为模 \(n\) 的缩系，且 \((m, n)=1\)，则 \(\lbrace ma_1, ma_2, \cdots, ma_{\varphi(n)}\rbrace\) 也为模 \(n\) 的缩系若 \(\lbrace a_1, a_2, \cdots, a_{\varphi(n)}\rbrace\) 为模 \(n\) 的缩系，则 \(\lbrace a_1^{-1}, a_2^{-1}, \cdots, a_{\varphi(n)}^{-1}\rbrace\) 也为模 \(n\) 的缩系

8. 中国剩余定理

已知 \(n_1,n_2\dots n_k\) 两两互质，同余方程组 \(\begin{cases}x\equiv a_1(\bmod n_1)\\[2ex]x\equiv a_2(\bmod n_2)\\[2ex]\cdots\\[2ex]x\equiv a_k(\bmod n_k)\\\end{cases}\) 在模 \(n=n_1n_2\dots n_k\) 的意义下有唯一解。具体的，设 \(M_i=\dfrac{n}{n_i}\)，\(N_i^{-1}\) 表示 \(M_i\) 在模 \(n_i\) 意义下的逆元。该方程的解为 \(\sum\limits_{i=1}^{k} a_iM_iM_i^{-1}\)。

9. Wilson

如果 \(p\) 是一个素数，则 \((p-1)!\equiv p-1\pmod p\)

10. 费马小定理

\(p\) 为质数，\(a\) 不是 \(p\) 的倍数，则 \(a^{p-1}\equiv 1\pmod p\)

11. 欧拉定理

\(a\) 和 \(n\) 为正整数，且 \((a, n)=1\)，则 \(a^{\varphi(n)}\equiv 1\pmod n\)

12. 同余的重要式子

若 \(a^m\equiv 1\pmod n,a^k\equiv 1\pmod n\Rightarrow a^{(m, k)}\equiv 1\pmod n\)

13. 阶

若 \((a, n)=1\)，且存在最小的正整数 \(k\)，使得 \(a^k\equiv 1\pmod n\)，且 \(a^n\equiv 1\pmod n\Leftrightarrow k|n\)，此时的 \(k\) 叫做 \(a\) 模 \(n\) 的阶。

群论1. 群的概念

群：集合 \(G\)，和运算 \(\ast\)，构成了一个群：\((G,\ast)\)。群满足下面的性质：运算封闭性： \(\forall x,y\in G,x\ast y\in G\)单位元： \(\exists e\in G,\forall g\in G,e\ast g=g\ast e=g\)逆元： \(\forall g\in G,\exists g"\in G,g\ast g"=g"\ast g=e\)，记作 \(g"=g^{-1}\)结合律： \(\forall g_1,g_2,g_3\in G,(g_1\ast g_2)\ast g_3=g_1\ast(g_2\ast g_3)\) 。可以证明单位元和逆元唯一。逆元的性质： \((a\ast b)^{-1}=b^{-1}\ast a^{-1}\)定义： \(a^b=\underbrace{a\ast a\ast a\cdots \ast a}_{b}\)\(|G|\) 有限为有限群(如 \((\mathbb{Z_n,+}),({\{a_1,\cdots,a_{\varphi(n)}\},\times })\))， \(|G|\) 无限为无限群(如 \((\mathbb{Z},+)\))。若 \(\forall a,b\in G,a\ast b=b\ast a\) 则称群 \((G,\ast)\) 为交换群（阿贝尔群）(如 \((\mathbb{Z},+)\))，否则称为非交换群(如 \((\mathbb{M_n},\times ),(\mathbb{S},\circ)\))。若 \(H\subseteq G,(H,\ast )\) 也是群，则称 \((H,\ast )\) 为 \((G,\ast)\) 的子群（如 \((\mathbb{Z},+)\) 的子群为 \((n\mathbb{Z},+),n\in\mathbb{Z}\) ）。循环群：若 \((G,\ast),G=\{a^m|m\in \mathbb{Z}\}\) 则称 \((G,\ast)\) 为循环群。记作 \((G,\ast)=\)，\(a\) 为群 \((G,\ast)\) 的生成元，循环群一定是交换群（如 \((\mathbb{Z},+)=<1>\) ）。同构： 存在双射 \(f:(G_1,\ast_1)\to (G_2,\ast_2)\) ,使得 \(\forall g_1,g_2\in G_1,f(g_1)\ast_2f(g_2)=f(g_1\ast_1 g_2)\)，则称 \((G_1,\ast_1)\) 和 \((G_2,\ast_2)\) 同构，记作 \((G_1,\ast_1)\cong (G_2,\ast_2)\) 。若两个循环群元素个数相同，则两个循环群同构，所以任意一个 \(n\) 个元素的循环群同构 \((\mathbb{Z_n},+)\),任意一个无限循环群同构 \((\mathbb{Z},+)\)。任意一个 \(n\) 个元素的循环群有 \(\varphi(n)\) 个生成元。任意一个非交换群都同构 \((\mathbb{S},\circ)\)若 \((H_1,\ast),(H_2,\ast)\) 均为 \((G,\ast)\) 的子群，则 \((H_1\cap H_2,\ast)\) 为 \((G,\ast)\) 的子群拉格朗日定理： 若 \((H,\ast)\) 为 \((G,\ast)\) 的子群，则 \(|H|\Big\vert |G|\) 。

2. 阶

阶：最小的 \(k\in \mathbb{N^{\ast}}\) 使得 \(g^k=e\)，则称 \(k\) 为 \(g\) 在群 \((G,\ast)\) 的阶，记作 \(o(g)\)。在 \((\mathbb{Z},+)\) 中，对于 \(g\ne 0,o(g)=+\infty\)在 \((G,\ast)\) 中，\(o(e)=1\)在交换群 \((G,\ast)\) 中，若 \(o(g)=n,o(g^k)=\dfrac{n}{\gcd(n,k)}\)在交换群 \((G,\ast)\) 中，\(\max\{o(g)|g\in G\}=\mathrm{lcm}\{o(g)|g\in G\}\)在交换群 \((G,\ast)\) 中，\(g_1,g_2\in G\),若 \(\gcd(o(g_1),o(g_2))=1,o(g_1\ast g_2)=o(g_1)o(g_2)\)

3. 置换群

定义置换 \(S_n\) 为双射 \(f:\{1\sim n\}\to \{1\sim n\}\) 。记作 \(\begin{pmatrix}1,2,\cdots n\\ a_1,a_2\cdots a_n\end{pmatrix}\) 表示 \(f(i)=a_i\) 。轮换：\((i_1,i_2,\cdots i_n)\) 为 \(f(i_j)=\begin{cases}i_{j+1}(j\ne n)\\i_1(j=n)\end{cases}\) 。\(\forall \alpha \in S_n\) \(\alpha\) 可以分解成若干个不相交轮换的乘积。不相交轮换的乘积具有交换律。若将 \(\alpha\in S\) 分解成若干个不相交轮换的乘积，即 \(\alpha=S_1\circ S_2\cdots S_k\) ，则 \(o(\alpha)=\mathrm{lcm}(|S_i|(1\le i\le k))\)

关键词：