20260214math

---
marp: true
theme: default
math: mathjax
---

# 2026/02/14 数学

---

# 数论基础

+ 最大公约数

+ 欧拉函数

+ 同余方程

+ 逆元

---

# 1. 最大公约数

**最大公约数**

欧几里得定理 / 辗转相除法：$\text{gcd}(a,b)=\text{gcd}(b,a\mod b)$

更相减损术（适用于大数计算）：$\text{gcd}(a,b)=\text{gcd}(a-b,b)$

+ 其需要结合 $\text{stein}$ 算法的优化：

    + 若 $2\mid a,\space 2\mid b$，则 $\text{gcd}(a,b)=2\times \text{gcd}(a/2,b/2)$

    + 若仅有 $2\mid a$，则 $\text{gcd}(a,b)=\text{gcd}(a/2,b)$

**最小公倍数**

$\text{gcd}(a,b)\times \text{lcm}(a,b)=a\times b$

---

**扩展欧几里得**

(将最大公约数与线性组合互相转化)

求 $ax+by=\text{gcd}(a,b)$ 的可行解

过程：

+ 令 $ax_1+by_1=\text{gcd}(a,b),bx_2+(a\mod b)y_2=\text{gcd}(b,a\mod b)$

+ 代入 $a\mod b=a-\lfloor\frac{a}{b}\rfloor\times b$，解得 $x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$

+ 不断递归直到 $b=0$，此时 $x=1,y=0$，向上传递。

**[P1292 倒酒](https://www.luogu.com.cn/problem/P1292)**

---

# 2. 欧拉函数

定义：$\varphi(n)=[1,n]$ 中与 $n$ 互质的数的个数

+ $n$ 为质数时有 $\varphi(n)=n-1$

性质:

+ 欧拉函数为积性函数，即当 $\text{gcd}(a,b)=1$ 时，$\varphi(a)\times \varphi(b)=\varphi(ab)$

	+ 结合素数筛线性预处理欧拉函数

---

+ $n=\sum_{d\mid n}\varphi(d)$

欧拉函数常常用于化简一列最大公约数的和：

$\text{gcd}(a,b)=\sum_{d\mid\text{gcd}(a,b)}\varphi(d)=\sum[d\mid a][d\mid b]\varphi(d)$


**[P2158 [SDOI2008] 仪仗队](https://www.luogu.com.cn/problem/P2158)**

**[P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398)**

---

+ $\sum\limits_1^n i[\text{gcd}(i,n)=1]=\frac{n}{2}\varphi(n)$

	+ 若 $\text{gcd}(i,n)=1$，则 $\text{gcd}(n-i,n)=1$

**[P1891 疯狂 LCM](https://www.luogu.com.cn/problem/P1891)**

---

**欧拉定理**

$\text{gcd}(a,m)=1$，有 $a^{\varphi(m)}\equiv 1\mod m$

+ 费马小定理为欧拉定理的特例

**扩展欧拉定理**

$$
a^k\equiv
\begin{cases}
a^{k\mod\varphi(m)} & \text{gcd}(a,m)=1 \\\\
a^k & \text{gcd}(a,m)\not=1,k<\varphi(m) \\\\
a^{(k\mod\varphi(m))+\varphi(m)} & \text{gcd}(a,m)\not=1,k\geq\varphi(m)
\end{cases}
\mod m
$$

**[P5091 【模板】扩展欧拉定理](https://www.luogu.com.cn/problem/P5091)**

---

# 3. 线性同余方程

**[P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)**

形如 $ax\equiv b\mod n$，找 $x\in[0,n-1]$ 的特解。

---

**1. 逆元法**：

+ 若 $\text{gcd}(a,n)=1$，则有唯一解 $x\equiv b\cdot a^{-1} \mod n$

+ 若 $\text{gcd}(a,n)=d>1$

    + $d\nmid b$，无解

    + $d\mid b$，将 $a,b,n$ 都除以 $d$，有 $a'x\equiv b'\mod n'$，此时 $\text{gcd}(a',n')=1$

---

**2. 不定方程求解**

+ 裴蜀定理：若 $a\times b\not=0$，则 $\text{gcd}(a,b)\mid ax+by$ 恒成立，且存在 $x,y$ 使得 $\text{gcd}(a,b)=ax+by$（可以推广到多个数）

    + **[P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)**

原式转化为 $ax+ny=b$，有解条件为 $\text{gcd}(a,n)\mid b$，从特解到通解易求。

**[P2421 [NOI2002] 荒岛野人](https://www.luogu.com.cn/problem/P2421)**

---

# 4. 逆元

**[P1082 [NOIP 2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)**

求解 $ax\equiv1\mod p$。

---

**1. 扩展欧几里得算法**

上式等价于 $ax+py=1$。

---

**2. 快速幂**

定理：只要 $p$ 为素数，即有 $a^m\equiv a \mod p$。

+ 费马小定理：$p$ 为素数，且 $p\nmid a$，则 $a^{m-1}\equiv 1\mod p$。

+ 扩展欧拉定理。

---

多个数求逆元：略

**线性预处理逆元**

+ $p=\lfloor\frac{p}{i}\rfloor i+(p\mod i)$
+ $\Rightarrow 0\equiv \lfloor\frac{p}{i}\rfloor i+(p\mod i)\mod p$
+ $\Rightarrow i^{-1}=-\lfloor\frac{p}{i}\rfloor(p\mod i)^{-1}$

易知 $p\mod i<i$，从 $1$ 开始递推即可。

**[P3811 【模板】模意义下的乘法逆元](https://www.luogu.com.cn/problem/P3811)**

---

# 组合计数基础

**加法原理**

完成任务的方法有 $n$ 类，每类有 $a_i$ 种方法，则完成任务的方法数为 $\sum a_i$ 种。

**乘法原理**

完成任务有 $n$ 个步骤，每个步骤有 $a_i$ 种方法，则完成任务的方案数为 $\prod a_i$ 种。

---

**$\text{A}$（排列数）**

从 $n$ 个元素中选出 $m$ 个进行排列（有序），则方案数为：

$A^n_m=n\times (n-1)\times ... \times (n-m)=\frac{n!}{m!}$

**$\text{C}$（组合数）**

从 $n$ 个元素中选出 $m$ 个元素组成一个集合（无序），则方案数为：

$C^n_m=\frac{A^n_m}{m!}=\frac{n!}{m!(n-m)!}$，也写作 $\binom{n}{m}$

---

组合数的性质：

+ $\binom{n}{m}=\binom{n}{n-m}$，即 $C_n^m=C_n^{n-m}$

+ $\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}$，即 $C_n^m=\frac{n}{m}C_{n-1}^{m-1}$

+ $\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$，即 $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$

  + 杨辉三角

---

**插板法**

用于处理将相同元素分组的计算技巧

Q1. 将 $n$ 个元素分为 $k$ 个非空组

<details>

可以理解为在 $n$ 个元素间（即 $n-1$ 个间隔空位上）插入 $k-1$ 个板作为分隔

</details>

Q2. 组可空

<details>

可能出现多个板放到同一个空位上的情况。

但反过来考虑，最终元素 + 板的数量一定为 $n+(k-1)$，即从最终状态倒推着看，是从 $n+(k-1)$ 个位置上选出 $k-1$ 个位置放板

</details>

---

Q3. 每组至少有 $a_i$ 个元素

<details>

预支元素，转化为 Q2。

</details>

Q4. 从 $n$ 个元素中选出 $k$ 个，要求互不相邻

<details>

剩余 $n-k$ 个挡板，划分成 $n-k+1$ 个空位，每个空位最多放一个。

</details>

---

**二项式定理**

$(a+b)^n=\sum_k \binom{n}{k} a^k b^{n-k}$

+ $2^n=(1+1)^n=\sum\limits_{i=0}^n\binom{n}{i}$

+ $0^n=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}=[n=0]$

---

## 容斥原理

$|\bigcup\limits_{i=1}^n S_i|=\sum\limits_{x=1}^{n}(-1)^{x-1}\sum
\limits_{a_i<a_{i+1}}|\bigcap\limits_{i=1}^nS_{a_i}|$

+ 每部分出现的次数（系数）为 $\binom{n}{1}-\binom{n}{2}+\binom{n}{3}-...$
+ $=\binom{n}{0}-\sum\limits_{i=1}^n(-1)^i\binom{n}{i}$

+ $=1-(1-1)^n$

**[P3197 [HNOI2008] 越狱](https://www.luogu.com.cn/problem/P3197)**

**[P1450 [HAOI2008] 硬币购物](https://www.luogu.com.cn/problem/P1450)**

**[P5664 [CSP-S 2019] Emiya 家今天的饭](https://www.luogu.com.cn/problem/P5664)**