# 信奥数学知识点详解（结论、证明与举例）

## 一、数论基础：质数、约数、唯一分解

### 1. 质数判定与筛法

#### （1）试除法判定质数
**结论**  
判断正整数 $n$ 是否为质数，只需检查 $2\sim\lfloor\sqrt{n}\rfloor$ 中是否存在 $n$ 的因子。可先特判 $n<2$ 和偶数 $n=2$，循环步长可优化为只试奇数。

**证明**  
若 $n$ 为合数，则存在 $d$ 满足 $d\mid n$ 且 $1<d<n$。令 $d\le \sqrt{n}$ 或 $n/d\le\sqrt{n}$ 必有一成立，因此只需枚举到 $\sqrt{n}$。条件 `i*i <= n` 可防溢出。

**举例**  
判断 $97$ 是否为质数：只需试除 $2,3,4,\dots,9$，均不能整除，故 $97$ 是质数。

> 实现代码见附录 1。

#### （2）埃氏筛法
**结论**  
求 $1\sim n$ 中所有质数，从小到大枚举每个数，若未被标记则记录为质数，并标记其所有倍数。时间复杂度 $O(n\log\log n)$。

**证明**  
每个质数 $p$ 会标记 $\frac{n}{p}$ 个合数，总操作次数 $\sum\_{p\le n}\frac{n}{p}\approx n\log\log n$。

**举例**  
筛出 $1\sim20$ 质数：保留 $2$，划去 $4,6,8,\dots$；保留 $3$，划去 $9,15,\dots$；最终得到 $2,3,5,7,11,13,17,19$。

> 实现代码见附录 2。

#### （3）欧拉筛（线性筛）
**结论**  
每个合数仅被其**最小质因子**筛除，时间复杂度 $O(n)$。实现时，对每个数 $i$ 乘上目前已存的质数 $p\_j$，当 $p\_j\mid i$ 时停止。

**证明**  
若 $i$ 的最小质因子为 $p\_j$，则 $i\times p\_{k}\;(k>j)$ 的最小质因子是 $p\_j$ 而非 $p\_k$，应留到后续用 $p\_j$ 筛除。该操作保证每个合数只被筛一次。

**举例**  
筛到 $i=9$ 时，质数表为 $2,3,5,7$；标记 $9\times2=18$，$9\times3=27$，此时 $3\mid9$ 停止，$9\times5=45$ 将留到 $i=15$ 时由质数 $3$ 筛去。

> 实现代码见附录 3。

### 2. 约数相关

#### （1）试除法枚举约数
**结论**  
求 $n$ 的所有约数，只需枚举 $1\sim\lfloor\sqrt{n}\rfloor$，若 $i\mid n$，则同时收集 $i$ 和 $n/i$（注意去重完全平方数）。

**证明**  
因子成对出现，每对至少有一个 $\le\sqrt{n}$。

**举例**  
$n=36$，枚举 $i=1,2,3,4,6$，得到约数集合 $\{1,36\},\{2,18\},\{3,12\},\{4,9\},\{6,6\}$，最终约数：$1,2,3,4,6,9,12,18,36$。

#### （2）约数个数与约数和公式
**结论**  
若唯一分解 $n = p\_1^{a\_1}p\_2^{a\_2}\cdots p\_k^{a\_k}$，则：  
约数个数 $d(n) = \prod\_{i=1}^k (a\_i+1)$  
约数和 $\sigma(n) = \prod\_{i=1}^k \frac{p\_i^{a\_i+1}-1}{p\_i-1}$

**证明**  
每个质因子指数可取 $0,1,\dots,a\_i$，由乘法原理得个数；约数和是每个质因子贡献的等比数列求和之积。

**举例**  
$n=12=2^2\times3^1$，约数个数 $(2+1)(1+1)=6$；约数和 $\frac{2^3-1}{2-1}\times\frac{3^2-1}{3-1}=7\times4=28$，验证：$1+2+3+4+6+12=28$。

#### （3）$10^9$ 范围内整数的最大约数个数
**结论**  
在不超过 $10^9$ 的整数中，约数个数最多的约为 **1536** 个（如 $73513440=2^5\cdot3^3\cdot5\cdot7\cdot11\cdot13\cdot17$，其约数个数为 $6\cdot4\cdot2\cdot2\cdot2\cdot2\cdot2=1536$）。

**举例**  
$735134400$（扩大10倍）已超 $10^9$，因此 $10^9$ 内最大约数个数为 1536，这一性质可用于估算枚举约数的上限。

### 3. 唯一分解定理
**结论**  
任意大于 1 的正整数 $n$ 可唯一表示为质数的幂乘积：
$n = p\_1^{a\_1}p\_2^{a\_2}\cdots p\_k^{a\_k}$
其中 $p\_1<p\_2<\cdots<p\_k$ 为质数，$a\_i\ge1$。$n=1$ 约定为空乘积。

**证明**  
存在性由强归纳法可证；唯一性源于质数的不可约性（欧几里得引理）。

**举例**  
$2024 = 2^3 \times 11 \times 23$。通过试除或 Pollard Rho 可得到分解。

---

## 二、GCD、LCM 与扩展欧几里得

### 1. 最大公约数与最小公倍数

#### （1）辗转相除法求 $\gcd(a,b)$
**结论**  
$\gcd(a,b) = \gcd(b, a\bmod b)$，反复应用直到 $b=0$，此时 $\gcd(a,0)=a$。时间复杂度 $O(\log \min(a,b))$。

**证明**  
设 $a=qb+r$，则 $d\mid a$ 且 $d\mid b \iff d\mid b$ 且 $d\mid r$，故公约数集合相同。

**举例**  
$\gcd(48,18)$：  
$48\bmod 18=12$  
$18\bmod 12=6$  
$12\bmod 6=0$ → 结果为 $6$。

> 实现代码见附录 4。

#### （2）LCM 计算与防溢出
**结论**  
$\operatorname{lcm}(a,b)=\frac{a}{\gcd(a,b)}\times b$，先除后乘可避免溢出。

**举例**  
$a=1000000000,\; b=1000000000$，直接乘会溢出，使用 $a/\gcd(a,b)*b = 1000000000$，正确。

#### （3）恒等式
**结论**  
$\gcd(a,b) \times \operatorname{lcm}(a,b) = a\times b$

**证明**  
设 $a=\gcd\cdot a',\; b=\gcd\cdot b'$ 且 $\gcd(a',b')=1$，则 $\operatorname{lcm}= \gcd\cdot a'\cdot b'$，乘积相等。

### 2. 裴蜀定理与扩展欧几里得

#### （1）不定方程有解条件
**结论**  
方程 $ax+by=c$ 有整数解的充要条件是 $\gcd(a,b)\mid c$。

**证明**  
必要性：任意整数组合 $ax+by$ 均是 $\gcd(a,b)$ 的倍数；  
充分性：扩展欧几里得可构造解。

**举例**  
$6x+15y=9$，$\gcd(6,15)=3\mid9$，有解；而 $6x+15y=5$ 无解。

#### （2）裴蜀定理
**结论**  
对任意整数 $a,b$，存在整数 $x,y$ 使 $ax+by=\gcd(a,b)$。

**举例**  
$6\times(-2) + 15\times1 = 3$。

#### （3）扩展欧几里得算法求解整数解
**结论**  
递归或迭代求出特解 $x\_0,y\_0$ 使得 $ax\_0+by\_0=\gcd$。通解为：
$x = x\_0 + \frac{b}{\gcd}t,\quad y = y\_0 - \frac{a}{\gcd}t$

**举例**  
解 $6x+15y=9$：先求 $6x'+15y'=3$ 得 $x'=-2,y'=1$，两边乘3得特解 $x=-6,y=3$。通解：$x=-6+5t,\; y=3-2t$。

> 实现代码见附录 5。

---

## 三、同余、欧拉函数、逆元与 CRT

### 1. 同余与模运算
**结论**  
若 $a\equiv b\pmod{m}$，则 $a+c\equiv b+c$，$a-c\equiv b-c$，$ac\equiv bc$（模 $m$ 下）。费马小定理：当 $p$ 为质数且 $p\nmid a$ 时，$a^{p-1}\equiv 1\pmod p$。可用于指数降幂：求 $a^b \bmod p$，当 $b$ 很大时，可降为 $a^{b\bmod (p-1)} \bmod p$（注意 $a$ 不能是 $p$ 的倍数）。

**举例**  
求 $2^{100}\bmod 7$：$p=7$，$2^6\equiv 1$，$100\bmod 6 = 4$，故 $2^{100}\equiv 2^4=16\equiv 2\pmod 7$。

### 2. 欧拉函数 $\varphi(n)$

**定义**  
$\varphi(n)$ 表示 $1\sim n$ 中与 $n$ 互质的数的个数。

**计算方式**  
若 $n = p\_1^{a\_1}p\_2^{a\_2}\cdots p\_k^{a\_k}$，则  
$\varphi(n) = n\prod\_{i=1}^k \left(1-\frac{1}{p\_i}\right)$

**积性性质辨析**  
当 $\gcd(m,n)=1$ 时，$\varphi(mn)=\varphi(m)\varphi(n)$（积性）。  
但若 $\gcd(m,n)\neq1$，则不一定成立。例如 $\varphi(2)=1,\varphi(4)=2$，而 $\varphi(8)=4 \neq \varphi(2)\varphi(4)=2$。因此不是完全积性。

**常用结论**  
$\sum\_{d\mid n}\varphi(d)=n$；小于 $n$ 且与 $n$ 互质的数之和为 $\frac{n\varphi(n)}{2}\;(n>1)$。

**举例**  
$\varphi(12)=12\times(1-\frac12)\times(1-\frac13)=12\times\frac12\times\frac23=4$，与12互质的数为1,5,7,11。

### 3. 乘法逆元

**定义**  
若 $b\times \operatorname{inv}(b)\equiv 1\pmod p$，则称 $\operatorname{inv}(b)$ 为 $b$ 模 $p$ 下的乘法逆元。

#### （1）费马小定理求逆元
**结论**  
当 $p$ 为质数且 $b\not\equiv0\pmod p$ 时，$\operatorname{inv}(b)=b^{p-2}\bmod p$。

**证明**  
由费马小定理 $b^{p-1}\equiv 1\pmod p$，两边乘 $b^{-1}$ 即得。

**举例**  
模 $7$ 下求 $3$ 的逆元：$3^{5}\bmod 7=243\bmod 7=5$，验证 $3\times5=15\equiv1\pmod7$。

#### （2）线性递推求 $1\sim n$ 逆元
**结论**  
对质数模 $p$，$1\sim n$ 的逆元可递推：  
$\operatorname{inv}[i] = \left(p - \left\lfloor\frac{p}{i}\right\rfloor\right) \times \operatorname{inv}[p\bmod i] \bmod p,\quad \operatorname{inv}[1]=1$

**证明**  
设 $p = k\cdot i + r\;(0<r<i)$，即 $k=\lfloor p/i\rfloor,\, r=p\bmod i$。  
$k\cdot i + r \equiv 0 \pmod p$ → $i\equiv -r\cdot k^{-1}$ → $i^{-1}\equiv -k\cdot r^{-1}\pmod p$，即上式。

**举例**  
模 $7$ 下计算 $\operatorname{inv}[1]$ 到 $\operatorname{inv}[6]$：  
1, 4 (因为 p - p/2=4, p%2=1的逆元1), 5 (p-p/3=5, inv[1]=1), 2, 3, 6。

> 递推代码见附录 6。

### 4. 中国剩余定理（CRT）

#### （1）经典 CRT（模数两两互质）
**结论**  
对同余方程组  
$x \equiv a\_i \pmod{m\_i},\quad i=1,2,\dots,k$  
若 $m\_i$ 两两互质，则模 $M=\prod m\_i$ 下存在唯一解。解为  
$x \equiv \sum\_{i=1}^k a\_i \cdot \frac{M}{m\_i} \cdot \operatorname{inv}\!\left(\frac{M}{m\_i},\, m\_i\right) \pmod M$

**举例**  
$x\equiv 2\pmod3,\;x\equiv 3\pmod5,\;x\equiv 2\pmod7$。  
$M=105$，$M\_1=35,\; \operatorname{inv}(35,3)=2$；$M\_2=21,\;\operatorname{inv}(21,5)=1$；$M\_3=15,\;\operatorname{inv}(15,7)=1$。  
$x=2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140+63+30=233\equiv 23\pmod{105}$。

#### （2）扩展 CRT（模数不互质）
**结论**  
当模数不互质时，需两两合并方程。已知 $x\equiv a\_1\pmod{m\_1}$，$x\equiv a\_2\pmod{m\_2}$，合并为模 $\operatorname{lcm}(m\_1,m\_2)$ 的新方程。利用扩展欧几里得求解 $t$ 使 $a\_1+m\_1t\equiv a\_2\pmod{m\_2}$，若 $\gcd(m\_1,m\_2)\nmid (a\_2-a\_1)$ 则无解。

**举例**  
$x\equiv 3\pmod6,\; x\equiv 5\pmod{10}$。$a\_2-a\_1=2$，$\gcd(6,10)=2\mid2$，解出 $t\equiv2\pmod5$，得 $x=3+6\cdot2=15\pmod{30}$。

---

## 四、进阶数论：整除分块与卢卡斯定理

### 1. 整除分块
**结论**  
求解 $\sum\_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor$ 时，$\lfloor n/i\rfloor$ 仅有 $O(\sqrt{n})$ 种取值。对于区间 $[l, r]$ 内所有 $i$，值相同，右端点公式  
$r = \left\lfloor \frac{n}{\lfloor n/l \rfloor} \right\rfloor$  
总时间复杂度 $O(\sqrt{n})$。

**证明**  
值的变化点位于 $i = \lfloor n/k\rfloor$ 附近，分块后可直接计算每段贡献。

**举例**  
$n=10$，块为：$l=1$ 值10，右端点 $r=\lfloor10/10\rfloor=1$；$l=2$ 值5，$r=\lfloor10/5\rfloor=2$；$l=3$ 值3，$r=\lfloor10/3\rfloor=3$；$l=4$ 值2，$r=\lfloor10/2\rfloor=5$；$l=6$ 值1，$r=10$。和=10+5+3+2+2+1+1+1+1+1=27。

> 实现代码见附录 7。

### 2. 卢卡斯定理

**结论**  
对于质数 $p$，有  
$\binom{n}{m} \bmod p = \binom{n \bmod p}{m \bmod p} \cdot \binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor} \bmod p$  
递归直到 $m=0$ 停止，$\binom{0}{0}=1$。

**适用条件**  
$p$ 为质数（通常 $p\le10^5$），$n,m$ 可极大（如 $10^{18}$）。

**举例**  
求 $\binom{10}{3}\bmod 7$。$10\bmod7=3$，$3\bmod7=3$，$\binom{3}{3}=1$；$\lfloor10/7\rfloor=1,\lfloor3/7\rfloor=0$，$\binom{1}{0}=1$，故结果为1。验证：$\binom{10}{3}=120\equiv1\pmod7$。

**大 $n$ 小 $m$ 组合数计算**  
当 $m$ 很小（相对 $p$）时，可直接用公式：$\binom{n}{m} = \frac{n(n-1)\cdots(n-m+1)}{m!} \bmod p$，分子分母均可暴力累乘，分母需乘逆元。

**举例**  
$\binom{10^9}{3} \bmod (10^9+7)$：分子为 $10^9\cdot(10^9-1)\cdot(10^9-2)$，分母 $6$ 的逆元乘入即可。

---

## 五、组合数学

### 1. 基础组合与排列

#### （1）组合数递推公式
**结论**  
$\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$，边界 $\binom{n}{0}=\binom{n}{n}=1$。

**证明**  
从 $n$ 个元素中选 $m$ 个，考虑是否包含第 $n$ 个元素。若包含，需从前 $n-1$ 个选 $m-1$；否则选 $m$ 个。

**举例**  
$\binom{5}{2}=\binom{4}{1}+\binom{4}{2}=4+6=10$。

#### （2）二项式定理
**结论**  
$(x+y)^n = \sum\_{k=0}^n \binom{n}{k} x^k y^{n-k}$，其中 $x^k y^{n-k}$ 的系数为 $\binom{n}{k}$。

**举例**  
$(x+y)^3 = \binom{3}{0}y^3 + \binom{3}{1}xy^2 + \binom{3}{2}x^2y + \binom{3}{3}x^3$。

#### （3）隔板法
**结论**  
- 将 $n$ 个相同球放入 $k$ 个不同盒子，每盒至少 1 个：方案数为 $\binom{n-1}{k-1}$（在 $n-1$ 个空隙插入 $k-1$ 个隔板）。  
- 允许空盒：相当于先借 $k$ 个球使每盒至少 1 个，方案数为 $\binom{n+k-1}{k-1}$。

**举例**  
10 个相同球放 3 个不同盒子，至少 1 个：$\binom{9}{2}=36$。允许空盒：$\binom{12}{2}=66$。

#### （4）不定方程非负整数解计数
**结论**  
方程 $x\_1+x\_2+\cdots+x\_k = n$ 的非负整数解个数等于 $\binom{n+k-1}{k-1}$（允许空盒的隔板法）。

**举例**  
$x\_1+x\_2+x\_3=5$ 的非负整数解有 $\binom{5+2}{2}=\binom{7}{2}=21$ 组。

### 2. 特殊排列与计数

#### （1）错位排列（德利克雷信封问题）
**结论**  
$n$ 个元素的错位排列数 $D(n)$ 满足递推式：  
$D(n) = (n-1)\big(D(n-1)+D(n-2)\big)$  
初始条件：$D(1)=0,\; D(2)=1$。$D(5)=44$。

**证明**  
考虑 1 号元素放在位置 $k\;(k\neq1)$，有两种情况：  
- 若 $k$ 号元素放在位置 1，则剩余 $n-2$ 个元素错排，方案数 $D(n-2)$；  
- 否则，相当于对除 1 号外的 $n-1$ 个元素进行错排（把 1 号的位置视为 $k$ 的“禁止位置”），方案数 $D(n-1)$。  
因 $k$ 有 $n-1$ 种选法，乘起来即得。

**举例**  
$D(3)=2$（排列 231, 312）；$D(5)=44$。

#### （2）不同球放相同盒子（非空）计数
**结论**  
将 $n$ 个不同球放入 $k$ 个相同盒子且不允许空盒，方案数为**第二类斯特林数** $S(n,k)$，满足  
$S(n,k) = S(n-1,k-1) + k\cdot S(n-1,k)$

**举例**  
$S(4,2)=7$：4 个不同球分成 2 个非空组，分组方式有 7 种。

### 3. 斯特林数与卡特兰数

#### （1）第一类与第二类斯特林数区别
- **第一类斯特林数** $s(n,k)$：将 $n$ 个元素分成 $k$ 个非空**轮换**（圆排列）的方案数。  
- **第二类斯特林数** $S(n,k)$：将 $n$ 个元素分成 $k$ 个非空**子集**的方案数。  
递推式分别为：  
$s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)$  
$S(n,k) = S(n-1,k-1) + k\,S(n-1,k)$

**举例**  
$n=4,k=2$：第一类 $s(4,2)=11$（11种轮换分组），第二类 $S(4,2)=7$。

#### （2）卡特兰数
**结论**  
第 $n$ 项卡特兰数通项：  
$C\_n = \frac{1}{n+1}\binom{2n}{n}$  
递推式：  
$C\_{n+1} = \sum\_{i=0}^{n} C\_i C\_{n-i},\quad C\_0=1$  
常用值：$C\_1=1, C\_2=2, C\_3=5, C\_4=14$。

**典型模型**：合法括号序列数、出栈序列数、凸多边形三角剖分数。

**举例**  
$n=4$ 个节点的二叉搜索树形态数为 $C\_4=14$；4 对括号的合法序列数也为 14。

### 4. 容斥原理

**结论**  
三个集合的并集大小：  
$|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$

**“至少一个满足”类问题转化**  
求至少满足一个性质的元素个数，可转化为 全集大小 - 都不满足的个数。

**举例**  
求 $1\sim100$ 中被 2,3,5 整除的数的个数。  
设 $A$:被2整除，$B$:被3整除，$C$:被5整除。  
$|A|=50,|B|=33,|C|=20$；  
$|A\cap B|=16$（6的倍数），$|A\cap C|=10$，$|B\cap C|=6$；  
$|A\cap B\cap C|=3$（30的倍数）。  
并集大小 $=50+33+20-16-10-6+3=74$。  
故 $1\sim100$ 中至少被一个整除的数有 74 个。

---

## 六、概率与期望

### 1. 期望的线性性质
**结论**  
对于任意随机变量 $X,Y$ 和常数 $a,b$，有  
$E(aX + bY) = aE(X) + bE(Y)$  
**成立条件**：期望存在即可，不要求 $X,Y$ 独立。

**举例**  
掷一枚均匀骰子，点数期望 $E(X)=3.5$。掷两枚骰子，点数和的期望 $E(X\_1+X\_2)=E(X\_1)+E(X\_2)=3.5+3.5=7$，无需考虑独立性。

### 2. 期望 DP 基础状态定义
**思想**  
将期望值作为状态值，根据全期望公式建立递推或方程。常见定义：设 $E[i]$ 表示从状态 $i$ 到达目标还需的期望步数（或期望花费）。

**举例**  
抛硬币直到出现正面，求期望次数。设期望 $E$，则有 $E = 1 + \frac12\cdot0 + \frac12\cdot E$，解得 $E=2$。

### 3. 带环期望 DP 的核心处理思想
**核心思想**  
当状态转移图中存在环时，不能简单顺序递推，需要将期望方程视为线性方程组，用**高斯消元**求解。或者利用**期望线性**和**待定系数法**将未知期望移到同侧解得显式表达式。

**举例**  
在一张有向图随机游走，从起点 1 走到终点 n 的期望步数。设 $E[i]$ 为从 $i$ 到 $n$ 的期望步数，有  
$E[i] = 1 + \frac{1}{\deg(i)}\sum\_{j} E[j]$（对出边求和），$E[n]=0$。  
此方程为线性方程组，若图有环则必须建矩阵求解（高斯消元）。更简单的环（如单环）可通过移项直接解出，如 $E[i] = 1 + pE[i] + (1-p)E[j]$ → $E[i] = \frac{1+(1-p)E[j]}{1-p}$。

---

## 附录：代码示例汇总

### 1. 试除法判定质数
```cpp
bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}
```

### 2. 埃氏筛法
```cpp
vector<int> prime;
bool isComp[MAXN];
void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isComp[i]) {
            prime.push\_back(i);
            for (int j = i * 2; j <= n; j += i)
                isComp[j] = true;
        }
    }
}
```

### 3. 欧拉筛
```cpp
vector<int> primes;
bool isComp[MAXN];
void euler(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isComp[i]) primes.push\_back(i);
        for (int p : primes) {
            if (i * p > n) break;
            isComp[i * p] = true;
            if (i % p == 0) break;
        }
    }
}
```

### 4. 辗转相除法
```cpp
int gcd(int a, int b) {
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}
```

### 5. 扩展欧几里得
```cpp
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
```

### 6. 线性递推逆元
```cpp
inv[1] = 1;
for (int i = 2; i <= n; ++i)
    inv[i] = (p - p / i) * inv[p % i] % p;
```

### 7. 整除分块
```cpp
long long sum = 0;
for (long long l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    sum += (r - l + 1) * (n / l);
}
```

信奥数学知识点详解（结论、证明与举例）

一、数论基础：质数、约数、唯一分解

1. 质数判定与筛法

（1）试除法判定质数

结论
判断正整数 $n$ 是否为质数，只需检查 $2\sim\lfloor\sqrt{n}\rfloor$ 中是否存在 $n$ 的因子。可先特判 $n<2$ 和偶数 $n=2$，循环步长可优化为只试奇数。

证明
若 $n$ 为合数，则存在 $d$ 满足 $d\mid n$ 且 $1<d<n$。令 $d\le \sqrt{n}$ 或 $n/d\le\sqrt{n}$ 必有一成立，因此只需枚举到 $\sqrt{n}$。条件 i*i <= n 可防溢出。

举例
判断 $97$ 是否为质数：只需试除 $2,3,4,\dots,9$，均不能整除，故 $97$ 是质数。

实现代码见附录 1。

（2）埃氏筛法

结论
求 $1\sim n$ 中所有质数，从小到大枚举每个数，若未被标记则记录为质数，并标记其所有倍数。时间复杂度 $O(n\log\log n)$。

证明
每个质数 $p$ 会标记 $\frac{n}{p}$ 个合数，总操作次数 $\sum_{p\le n}\frac{n}{p}\approx n\log\log n$。

举例
筛出 $1\sim20$ 质数：保留 $2$，划去 $4,6,8,\dots$；保留 $3$，划去 $9,15,\dots$；最终得到 $2,3,5,7,11,13,17,19$。

实现代码见附录 2。

（3）欧拉筛（线性筛）

结论
每个合数仅被其最小质因子筛除，时间复杂度 $O(n)$。实现时，对每个数 $i$ 乘上目前已存的质数 $p_j$，当 $p_j\mid i$ 时停止。

证明
若 $i$ 的最小质因子为 $p_j$，则 $i\times p_{k}\;(k>j)$ 的最小质因子是 $p_j$ 而非 $p_k$，应留到后续用 $p_j$ 筛除。该操作保证每个合数只被筛一次。

举例
筛到 $i=9$ 时，质数表为 $2,3,5,7$；标记 $9\times2=18$，$9\times3=27$，此时 $3\mid9$ 停止，$9\times5=45$ 将留到 $i=15$ 时由质数 $3$ 筛去。

实现代码见附录 3。

2. 约数相关

（1）试除法枚举约数

结论
求 $n$ 的所有约数，只需枚举 $1\sim\lfloor\sqrt{n}\rfloor$，若 $i\mid n$，则同时收集 $i$ 和 $n/i$（注意去重完全平方数）。

证明
因子成对出现，每对至少有一个 $\le\sqrt{n}$。

举例
$n=36$，枚举 $i=1,2,3,4,6$，得到约数集合 ${1,36},{2,18},{3,12},{4,9},{6,6}$，最终约数：$1,2,3,4,6,9,12,18,36$。

（2）约数个数与约数和公式

结论
若唯一分解 $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，则：
约数个数 $d(n) = \prod_{i=1}^k (a_i+1)$
约数和 $\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i+1}-1}{p_i-1}$

证明
每个质因子指数可取 $0,1,\dots,a_i$，由乘法原理得个数；约数和是每个质因子贡献的等比数列求和之积。

举例
$n=12=2^2\times3^1$，约数个数 $(2+1)(1+1)=6$；约数和 $\frac{2^3-1}{2-1}\times\frac{3^2-1}{3-1}=7\times4=28$，验证：$1+2+3+4+6+12=28$。

（3）$10^9$ 范围内整数的最大约数个数

结论
在不超过 $10^9$ 的整数中，约数个数最多的约为 1536 个（如 $73513440=2^5\cdot3^3\cdot5\cdot7\cdot11\cdot13\cdot17$，其约数个数为 $6\cdot4\cdot2\cdot2\cdot2\cdot2\cdot2=1536$）。

举例
$735134400$（扩大10倍）已超 $10^9$，因此 $10^9$ 内最大约数个数为 1536，这一性质可用于估算枚举约数的上限。

3. 唯一分解定理

结论
任意大于 1 的正整数 $n$ 可唯一表示为质数的幂乘积： $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ 其中 $p_1<p_2<\cdots<p_k$ 为质数，$a_i\ge1$。$n=1$ 约定为空乘积。

证明
存在性由强归纳法可证；唯一性源于质数的不可约性（欧几里得引理）。

举例
$2024 = 2^3 \times 11 \times 23$。通过试除或 Pollard Rho 可得到分解。

二、GCD、LCM 与扩展欧几里得

1. 最大公约数与最小公倍数

（1）辗转相除法求 $\gcd(a,b)$

结论
$\gcd(a,b) = \gcd(b, a\bmod b)$，反复应用直到 $b=0$，此时 $\gcd(a,0)=a$。时间复杂度 $O(\log \min(a,b))$。

证明
设 $a=qb+r$，则 $d\mid a$ 且 $d\mid b \iff d\mid b$ 且 $d\mid r$，故公约数集合相同。

举例
$\gcd(48,18)$：
$48\bmod 18=12$
$18\bmod 12=6$
$12\bmod 6=0$ → 结果为 $6$。

实现代码见附录 4。

（2）LCM 计算与防溢出

结论
$\operatorname{lcm}(a,b)=\frac{a}{\gcd(a,b)}\times b$，先除后乘可避免溢出。

举例
$a=1000000000,\; b=1000000000$，直接乘会溢出，使用 $a/\gcd(a,b)*b = 1000000000$，正确。

（3）恒等式

结论
$\gcd(a,b) \times \operatorname{lcm}(a,b) = a\times b$

证明
设 $a=\gcd\cdot a',\; b=\gcd\cdot b'$ 且 $\gcd(a',b')=1$，则 $\operatorname{lcm}= \gcd\cdot a'\cdot b'$，乘积相等。

2. 裴蜀定理与扩展欧几里得

（1）不定方程有解条件

结论
方程 $ax+by=c$ 有整数解的充要条件是 $\gcd(a,b)\mid c$。

证明
必要性：任意整数组合 $ax+by$ 均是 $\gcd(a,b)$ 的倍数；
充分性：扩展欧几里得可构造解。

举例
$6x+15y=9$，$\gcd(6,15)=3\mid9$，有解；而 $6x+15y=5$ 无解。

（2）裴蜀定理

结论
对任意整数 $a,b$，存在整数 $x,y$ 使 $ax+by=\gcd(a,b)$。

举例
$6\times(-2) + 15\times1 = 3$。

（3）扩展欧几里得算法求解整数解

结论
递归或迭代求出特解 $x_0,y_0$ 使得 $ax_0+by_0=\gcd$。通解为： $x = x_0 + \frac{b}{\gcd}t,\quad y = y_0 - \frac{a}{\gcd}t$

举例
解 $6x+15y=9$：先求 $6x'+15y'=3$ 得 $x'=-2,y'=1$，两边乘3得特解 $x=-6,y=3$。通解：$x=-6+5t,\; y=3-2t$。

实现代码见附录 5。

三、同余、欧拉函数、逆元与 CRT

1. 同余与模运算

结论
若 $a\equiv b\pmod{m}$，则 $a+c\equiv b+c$，$a-c\equiv b-c$，$ac\equiv bc$（模 $m$ 下）。费马小定理：当 $p$ 为质数且 $p\nmid a$ 时，$a^{p-1}\equiv 1\pmod p$。可用于指数降幂：求 $a^b \bmod p$，当 $b$ 很大时，可降为 $a^{b\bmod (p-1)} \bmod p$（注意 $a$ 不能是 $p$ 的倍数）。

举例
求 $2^{100}\bmod 7$：$p=7$，$2^6\equiv 1$，$100\bmod 6 = 4$，故 $2^{100}\equiv 2^4=16\equiv 2\pmod 7$。

2. 欧拉函数 $\varphi(n)$

定义
$\varphi(n)$ 表示 $1\sim n$ 中与 $n$ 互质的数的个数。

计算方式
若 $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，则
$\varphi(n) = n\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)$

积性性质辨析
当 $\gcd(m,n)=1$ 时，$\varphi(mn)=\varphi(m)\varphi(n)$（积性）。
但若 $\gcd(m,n)\neq1$，则不一定成立。例如 $\varphi(2)=1,\varphi(4)=2$，而 $\varphi(8)=4 \neq \varphi(2)\varphi(4)=2$。因此不是完全积性。

常用结论
$\sum_{d\mid n}\varphi(d)=n$；小于 $n$ 且与 $n$ 互质的数之和为 $\frac{n\varphi(n)}{2}\;(n>1)$。

举例
$\varphi(12)=12\times(1-\frac12)\times(1-\frac13)=12\times\frac12\times\frac23=4$，与12互质的数为1,5,7,11。

3. 乘法逆元

定义
若 $b\times \operatorname{inv}(b)\equiv 1\pmod p$，则称 $\operatorname{inv}(b)$ 为 $b$ 模 $p$ 下的乘法逆元。

（1）费马小定理求逆元

结论
当 $p$ 为质数且 $b\not\equiv0\pmod p$ 时，$\operatorname{inv}(b)=b^{p-2}\bmod p$。

证明
由费马小定理 $b^{p-1}\equiv 1\pmod p$，两边乘 $b^{-1}$ 即得。

举例
模 $7$ 下求 $3$ 的逆元：$3^{5}\bmod 7=243\bmod 7=5$，验证 $3\times5=15\equiv1\pmod7$。

（2）线性递推求 $1\sim n$ 逆元

结论
对质数模 $p$，$1\sim n$ 的逆元可递推：
$\operatorname{inv}[i] = \left(p - \left\lfloor\frac{p}{i}\right\rfloor\right) \times \operatorname{inv}[p\bmod i] \bmod p,\quad \operatorname{inv}[1]=1$

证明
设 $p = k\cdot i + r\;(0<r<i)$，即 $k=\lfloor p/i\rfloor,\, r=p\bmod i$。
$k\cdot i + r \equiv 0 \pmod p$ → $i\equiv -r\cdot k^{-1}$ → $i^{-1}\equiv -k\cdot r^{-1}\pmod p$，即上式。

举例
模 $7$ 下计算 $\operatorname{inv}[1]$ 到 $\operatorname{inv}[6]$：
1, 4 (因为 p - p/2=4, p%2=1的逆元1), 5 (p-p/3=5, inv[1]=1), 2, 3, 6。

递推代码见附录 6。

4. 中国剩余定理（CRT）

（1）经典 CRT（模数两两互质）

结论
对同余方程组
$x \equiv a_i \pmod{m_i},\quad i=1,2,\dots,k$
若 $m_i$ 两两互质，则模 $M=\prod m_i$ 下存在唯一解。解为
$x \equiv \sum_{i=1}^k a_i \cdot \frac{M}{m_i} \cdot \operatorname{inv}!\left(\frac{M}{m_i},\, m_i\right) \pmod M$

举例
$x\equiv 2\pmod3,\;x\equiv 3\pmod5,\;x\equiv 2\pmod7$。
$M=105$，$M_1=35,\; \operatorname{inv}(35,3)=2$；$M_2=21,\;\operatorname{inv}(21,5)=1$；$M_3=15,\;\operatorname{inv}(15,7)=1$。
$x=2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140+63+30=233\equiv 23\pmod{105}$。

（2）扩展 CRT（模数不互质）

结论
当模数不互质时，需两两合并方程。已知 $x\equiv a_1\pmod{m_1}$，$x\equiv a_2\pmod{m_2}$，合并为模 $\operatorname{lcm}(m_1,m_2)$ 的新方程。利用扩展欧几里得求解 $t$ 使 $a_1+m_1t\equiv a_2\pmod{m_2}$，若 $\gcd(m_1,m_2)\nmid (a_2-a_1)$ 则无解。

举例
$x\equiv 3\pmod6,\; x\equiv 5\pmod{10}$。$a_2-a_1=2$，$\gcd(6,10)=2\mid2$，解出 $t\equiv2\pmod5$，得 $x=3+6\cdot2=15\pmod{30}$。

四、进阶数论：整除分块与卢卡斯定理

1. 整除分块

结论
求解 $\sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor$ 时，$\lfloor n/i\rfloor$ 仅有 $O(\sqrt{n})$ 种取值。对于区间 $[l, r]$ 内所有 $i$，值相同，右端点公式
$r = \left\lfloor \frac{n}{\lfloor n/l \rfloor} \right\rfloor$
总时间复杂度 $O(\sqrt{n})$。

证明
值的变化点位于 $i = \lfloor n/k\rfloor$ 附近，分块后可直接计算每段贡献。

举例
$n=10$，块为：$l=1$ 值10，右端点 $r=\lfloor10/10\rfloor=1$；$l=2$ 值5，$r=\lfloor10/5\rfloor=2$；$l=3$ 值3，$r=\lfloor10/3\rfloor=3$；$l=4$ 值2，$r=\lfloor10/2\rfloor=5$；$l=6$ 值1，$r=10$。和=10+5+3+2+2+1+1+1+1+1=27。

实现代码见附录 7。

2. 卢卡斯定理

结论
对于质数 $p$，有
$\binom{n}{m} \bmod p = \binom{n \bmod p}{m \bmod p} \cdot \binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor} \bmod p$
递归直到 $m=0$ 停止，$\binom{0}{0}=1$。

适用条件
$p$ 为质数（通常 $p\le10^5$），$n,m$ 可极大（如 $10^{18}$）。

举例
求 $\binom{10}{3}\bmod 7$。$10\bmod7=3$，$3\bmod7=3$，$\binom{3}{3}=1$；$\lfloor10/7\rfloor=1,\lfloor3/7\rfloor=0$，$\binom{1}{0}=1$，故结果为1。验证：$\binom{10}{3}=120\equiv1\pmod7$。

大 $n$ 小 $m$ 组合数计算
当 $m$ 很小（相对 $p$）时，可直接用公式：$\binom{n}{m} = \frac{n(n-1)\cdots(n-m+1)}{m!} \bmod p$，分子分母均可暴力累乘，分母需乘逆元。

举例
$\binom{10^9}{3} \bmod (10^9+7)$：分子为 $10^9\cdot(10^9-1)\cdot(10^9-2)$，分母 $6$ 的逆元乘入即可。

五、组合数学

1. 基础组合与排列

（1）组合数递推公式

结论
$\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$，边界 $\binom{n}{0}=\binom{n}{n}=1$。

证明
从 $n$ 个元素中选 $m$ 个，考虑是否包含第 $n$ 个元素。若包含，需从前 $n-1$ 个选 $m-1$；否则选 $m$ 个。

举例
$\binom{5}{2}=\binom{4}{1}+\binom{4}{2}=4+6=10$。

（2）二项式定理

结论
$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$，其中 $x^k y^{n-k}$ 的系数为 $\binom{n}{k}$。

举例
$(x+y)^3 = \binom{3}{0}y^3 + \binom{3}{1}xy^2 + \binom{3}{2}x^2y + \binom{3}{3}x^3$。

（3）隔板法

结论
- 将 $n$ 个相同球放入 $k$ 个不同盒子，每盒至少 1 个：方案数为 $\binom{n-1}{k-1}$（在 $n-1$ 个空隙插入 $k-1$ 个隔板）。
- 允许空盒：相当于先借 $k$ 个球使每盒至少 1 个，方案数为 $\binom{n+k-1}{k-1}$。

举例
10 个相同球放 3 个不同盒子，至少 1 个：$\binom{9}{2}=36$。允许空盒：$\binom{12}{2}=66$。

（4）不定方程非负整数解计数

结论
方程 $x_1+x_2+\cdots+x_k = n$ 的非负整数解个数等于 $\binom{n+k-1}{k-1}$（允许空盒的隔板法）。

举例
$x_1+x_2+x_3=5$ 的非负整数解有 $\binom{5+2}{2}=\binom{7}{2}=21$ 组。

2. 特殊排列与计数

（1）错位排列（德利克雷信封问题）

结论
$n$ 个元素的错位排列数 $D(n)$ 满足递推式：
$D(n) = (n-1)\big(D(n-1)+D(n-2)\big)$
初始条件：$D(1)=0,\; D(2)=1$。$D(5)=44$。

证明
考虑 1 号元素放在位置 $k\;(k\neq1)$，有两种情况：
- 若 $k$ 号元素放在位置 1，则剩余 $n-2$ 个元素错排，方案数 $D(n-2)$；
- 否则，相当于对除 1 号外的 $n-1$ 个元素进行错排（把 1 号的位置视为 $k$ 的“禁止位置”），方案数 $D(n-1)$。
因 $k$ 有 $n-1$ 种选法，乘起来即得。

举例
$D(3)=2$（排列 231, 312）；$D(5)=44$。

（2）不同球放相同盒子（非空）计数

结论
将 $n$ 个不同球放入 $k$ 个相同盒子且不允许空盒，方案数为第二类斯特林数 $S(n,k)$，满足
$S(n,k) = S(n-1,k-1) + k\cdot S(n-1,k)$

举例
$S(4,2)=7$：4 个不同球分成 2 个非空组，分组方式有 7 种。

3. 斯特林数与卡特兰数

（1）第一类与第二类斯特林数区别

第一类斯特林数 $s(n,k)$：将 $n$ 个元素分成 $k$ 个非空轮换（圆排列）的方案数。
第二类斯特林数 $S(n,k)$：将 $n$ 个元素分成 $k$ 个非空子集的方案数。
递推式分别为：
$s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)$
$S(n,k) = S(n-1,k-1) + k\,S(n-1,k)$

举例
$n=4,k=2$：第一类 $s(4,2)=11$（11种轮换分组），第二类 $S(4,2)=7$。

（2）卡特兰数

结论
第 $n$ 项卡特兰数通项：
$C_n = \frac{1}{n+1}\binom{2n}{n}$
递推式：
$C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i},\quad C_0=1$
常用值：$C_1=1, C_2=2, C_3=5, C_4=14$。

典型模型：合法括号序列数、出栈序列数、凸多边形三角剖分数。

举例
$n=4$ 个节点的二叉搜索树形态数为 $C_4=14$；4 对括号的合法序列数也为 14。

4. 容斥原理

结论
三个集合的并集大小：
$|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$

“至少一个满足”类问题转化
求至少满足一个性质的元素个数，可转化为全集大小 - 都不满足的个数。

举例
求 $1\sim100$ 中被 2,3,5 整除的数的个数。
设 $A$:被2整除，$B$:被3整除，$C$:被5整除。
$|A|=50,|B|=33,|C|=20$；
$|A\cap B|=16$（6的倍数），$|A\cap C|=10$，$|B\cap C|=6$；
$|A\cap B\cap C|=3$（30的倍数）。
并集大小 $=50+33+20-16-10-6+3=74$。
故 $1\sim100$ 中至少被一个整除的数有 74 个。

六、概率与期望

1. 期望的线性性质

结论
对于任意随机变量 $X,Y$ 和常数 $a,b$，有
$E(aX + bY) = aE(X) + bE(Y)$
成立条件：期望存在即可，不要求 $X,Y$ 独立。

举例
掷一枚均匀骰子，点数期望 $E(X)=3.5$。掷两枚骰子，点数和的期望 $E(X_1+X_2)=E(X_1)+E(X_2)=3.5+3.5=7$，无需考虑独立性。

2. 期望 DP 基础状态定义

思想
将期望值作为状态值，根据全期望公式建立递推或方程。常见定义：设 $E[i]$ 表示从状态 $i$ 到达目标还需的期望步数（或期望花费）。

举例
抛硬币直到出现正面，求期望次数。设期望 $E$，则有 $E = 1 + \frac12\cdot0 + \frac12\cdot E$，解得 $E=2$。

3. 带环期望 DP 的核心处理思想

核心思想
当状态转移图中存在环时，不能简单顺序递推，需要将期望方程视为线性方程组，用高斯消元求解。或者利用期望线性和待定系数法将未知期望移到同侧解得显式表达式。

举例
在一张有向图随机游走，从起点 1 走到终点 n 的期望步数。设 $E[i]$ 为从 $i$ 到 $n$ 的期望步数，有
$E[i] = 1 + \frac{1}{\deg(i)}\sum_{j} E[j]$（对出边求和），$E[n]=0$。
此方程为线性方程组，若图有环则必须建矩阵求解（高斯消元）。更简单的环（如单环）可通过移项直接解出，如 $E[i] = 1 + pE[i] + (1-p)E[j]$ → $E[i] = \frac{1+(1-p)E[j]}{1-p}$。

附录：代码示例汇总

1. 试除法判定质数

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}

2. 埃氏筛法

vector<int> prime;
bool isComp[MAXN];
void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isComp[i]) {
            prime.push\_back(i);
            for (int j = i * 2; j <= n; j += i)
                isComp[j] = true;
        }
    }
}

3. 欧拉筛

vector<int> primes;
bool isComp[MAXN];
void euler(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isComp[i]) primes.push\_back(i);
        for (int p : primes) {
            if (i * p > n) break;
            isComp[i * p] = true;
            if (i % p == 0) break;
        }
    }
}

4. 辗转相除法

int gcd(int a, int b) {
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}

5. 扩展欧几里得

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

6. 线性递推逆元

inv[1] = 1;
for (int i = 2; i <= n; ++i)
    inv[i] = (p - p / i) * inv[p % i] % p;

7. 整除分块

long long sum = 0;
for (long long l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    sum += (r - l + 1) * (n / l);
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

CSP信奥数学（快速对战）