# 数学知识模块讲义

本模块包含 **质数、约数、欧拉函数、快速幂、扩展欧几里得算法、中国剩余定理、高斯消元、求组合数、容斥原理、博弈论** 共 10 个核心数学与数论算法。这些知识在信息学竞赛中往往是拉开差距的关键。

---

## 1. 质数 (Prime Numbers)

### 概念与判定
* **质数**：大于 1 的整数，除了 1 和它本身外，没有其他因数。
* **试除法判定**：如果要判断一个数 $n$ 是不是质数，不需要从 2 检查到 $n-1$，只需要检查到 **$\sqrt{n}$** 即可。
  * **数学原理**：如果 $n = a \times b$，那么 $a$ 和 $b$ 中必然有一个小于或等于 $\sqrt{n}$。
  ```cpp
  bool is_prime(int n) {
      if (n < 2) return false;
      for (int i = 2; i <= n / i; i++) // 写成 i <= n / i 防止 i * i 溢出
          if (n % i == 0) return false;
      return true;
  }
  ```
* **筛法求质数**：想求 $1 \sim N$ 之间有多少个质数？用**欧拉筛（线性筛）**，核心思想是**让每个合数只被它的最小质因数筛掉一次**，保证时间复杂度为 $O(N)$。

---

## 2. 约数 (Divisors)

### 求一个数的所有约数
同样利用 $\sqrt{n}$ 的性质：如果 $d$ 能整除 $n$，那么 $\frac{n}{d}$ 也一定能整除 $n$。我们只需要从小到大遍历到 $\sqrt{n}$ 即可成对找出所有约数。

### 约数个数定理与约数之和定理
任何一个大于 1 的正整数都可以唯一分解为质因数相乘的形式：
$$N = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$$
1. **约数总个数**：
   $$\text{Count} = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$$
2. **所有约数之和**：
   $$\text{Sum} = (1 + p_1 + p_1^2 + \dots + p_1^{a_1}) \cdots (1 + p_k + p_k^2 + \dots + p_k^{a_k})$$

---

## 3. 欧拉函数 (Euler's Totient Function)

### 概念与公式
* **定义**：$\varphi(n)$ 表示在 $1 \sim n$ 中，和 $n$ **互质**（即最大公约数为 1）的整数个数。
* **计算公式**：
  $$\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$$
  其中 $p_1, p_2, \dots, p_k$ 是 $n$ 的所有不同质因数。
* **性质**：如果 $n$ 是质数，那么 $\varphi(n) = n - 1$。

---

## 4. 快速幂 (Fast Exponentiation)

### 核心思想
怎么光速计算 $3^{1000000000} \pmod p$？如果连乘会超时。
快速幂利用了**指数的二进制拆分**。
* 例如求 $3^{10}$，$10$ 的二进制是 `1010`（即 $8 + 2$）。
* 那么 $3^{10} = 3^8 \times 3^2$。我们每次把底数平方（$3 \to 9 \to 81 \dots$），根据指数二进制位是 1 还是 0 决定要不要乘进答案里。
* 时间复杂度：**$O(\log n)$**。

```cpp
typedef long long LL;
LL qmi(LL a, LL k, LL p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = (res * a) % p;
        a = (a * a) % p;
        k >>= 1;
    }
    return res;
}
```

---

## 5. 扩展欧几里得算法 (Extended Euclidean Algorithm)

### 作用
裴蜀定理告诉我们：对于任意正整数 $a, b$，必然存在整数 $x, y$，满足：
$$ax + by = \gcd(a, b)$$
**扩展欧几里得算法**不仅能求出 $\gcd(a, b)$，还能顺便求出方程中的一组解 $x$ 和 $y$。这在密码学（如计算**乘法逆元**、RSA 加密）中至关重要。

---

## 6. 中国剩余定理 (Chinese Remainder Theorem, CRT)

### 场景与公式
用来求解形如以下的**同余方程组**：
$$\begin{cases} 
x \equiv a_1 \pmod{m_1} \\ 
x \equiv a_2 \pmod{m_2} \\ 
\dots \\ 
x \equiv a_k \pmod{m_k} 
\end{cases}$$
（其中模数 $m_1, m_2, \dots, m_k$ 两两互质）。

### 构造法解题步骤
1. 计算所有模数的乘积：$M = m_1 \cdot m_2 \cdots m_k$。
2. 对于第 $i$ 个方程，计算 $M_i = \frac{M}{m_i}$。
3. 求 $M_i$ 在模 $m_i$ 意义下的**乘法逆元** $t_i$（满足 $M_i \cdot t_i \equiv 1 \pmod{m_i}$）。
4. 方程组在模 $M$ 意义下的唯一解为：
   $$x = \sum_{i=1}^{k} a_i \cdot M_i \cdot t_i \pmod M$$

---

## 7. 高斯消元 (Gaussian Elimination)

### 作用
用来求解 $N$ 元一次方程组，或者求矩阵的秩、逆矩阵。
### 核心思想
利用初中学的“加减消元法”，把复杂的方程组通过行变换化简成**阶梯型矩阵**：
```
1x + 2y + 3z = 6
     0y + 4z = 4
          0z = 0  (无解或无数解)
```
最后从下往上“回代”求出每个未知数的值。

---

## 8. 求组合数 (Combinatorics)

### 概念
从 $a$ 个不同物品中选出 $b$ 个物品的方案数，记作 $C_a^b$ 或 $\binom{a}{b}$：
$$\binom{a}{b} = \frac{a!}{b!(a-b)!}$$

### 不同情况下的求法
1. **递推法（杨辉三角，适合数字较小）**：
   $$\binom{a}{b} = \binom{a-1}{b-1} + \binom{a-1}{b}$$
2. **费马小定理求逆元（适合 $a, b$ 很大，模数是质数）**：
   把除法转换成乘法逆元：$\binom{a}{b} \equiv a! \cdot (b!)^{-1} \cdot ((a-b)!)^{-1} \pmod p$。
3. **卢卡斯定理 (Lucas Theorem)**：适合模数 $p$ 较小但 $a, b$ 极其巨大的情况。

---

## 9. 容斥原理 (Inclusion-Exclusion Principle)

### 核心思想
算几个集合的并集大小时，避免重复计算。
* **两个集合**：$|A \cup B| = |A| + |B| - |A \cap B|$
* **三个集合**：
  $$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$$
* **核心规律**：“**奇加偶减**”——交集个数为奇数个集合的大小相加，交集个数为偶数个集合的大小相减。

---

## 10. 博弈论 (Game Theory)

### 两个经典博弈模型
1. **巴什游戏 (Bash Game)**：
   * 一堆石子共 $n$ 个，两人轮流拿，每次最少拿 1 个，最多拿 $m$ 个，拿走最后一个的人赢。
   * **结论**：如果 $n$ 是 $(m+1)$ 的倍数，先手必输，否则先手必赢。
2. **Nim 游戏**：
   * 有多堆石子，每次可以从任意一堆里拿任意个石子，最后拿光者胜。
   * **结论**：把所有堆的石子数量做**异或和**：
     $$S = a_1 \mathbin{\hat{}} a_2 \mathbin{\hat{}} \dots \mathbin{\hat{}} a_n$$
     如果 $S \neq 0$，先手必胜；如果 $S = 0$，先手必败。

---

数学知识模块讲义

本模块包含 质数、约数、欧拉函数、快速幂、扩展欧几里得算法、中国剩余定理、高斯消元、求组合数、容斥原理、博弈论 共 10 个核心数学与数论算法。这些知识在信息学竞赛中往往是拉开差距的关键。

1. 质数 (Prime Numbers)

概念与判定

质数：大于 1 的整数，除了 1 和它本身外，没有其他因数。
试除法判定：如果要判断一个数 $n$ 是不是质数，不需要从 2 检查到 $n-1$，只需要检查到 $\sqrt{n}$ 即可。
数学原理：如果 $n = a \times b$，那么 $a$ 和 $b$ 中必然有一个小于或等于 $\sqrt{n}$。 cpp bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) // 写成 i <= n / i 防止 i * i 溢出 if (n % i == 0) return false; return true; }
筛法求质数：想求 $1 \sim N$ 之间有多少个质数？用欧拉筛（线性筛），核心思想是让每个合数只被它的最小质因数筛掉一次，保证时间复杂度为 $O(N)$。

2. 约数 (Divisors)

求一个数的所有约数

同样利用 $\sqrt{n}$ 的性质：如果 $d$ 能整除 $n$，那么 $\frac{n}{d}$ 也一定能整除 $n$。我们只需要从小到大遍历到 $\sqrt{n}$ 即可成对找出所有约数。

约数个数定理与约数之和定理

任何一个大于 1 的正整数都可以唯一分解为质因数相乘的形式： $$N = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$$ 1. 约数总个数： $$\text{Count} = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$$ 2. 所有约数之和： $$\text{Sum} = (1 + p_1 + p_1^2 + \dots + p_1^{a_1}) \cdots (1 + p_k + p_k^2 + \dots + p_k^{a_k})$$

3. 欧拉函数 (Euler's Totient Function)

概念与公式

定义：$\varphi(n)$ 表示在 $1 \sim n$ 中，和 $n$ 互质（即最大公约数为 1）的整数个数。
计算公式： $$\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$$ 其中 $p_1, p_2, \dots, p_k$ 是 $n$ 的所有不同质因数。
性质：如果 $n$ 是质数，那么 $\varphi(n) = n - 1$。

4. 快速幂 (Fast Exponentiation)

核心思想

怎么光速计算 $3^{1000000000} \pmod p$？如果连乘会超时。快速幂利用了指数的二进制拆分。 * 例如求 $3^{10}$，$10$ 的二进制是 1010（即 $8 + 2$）。 * 那么 $3^{10} = 3^8 \times 3^2$。我们每次把底数平方（$3 \to 9 \to 81 \dots$），根据指数二进制位是 1 还是 0 决定要不要乘进答案里。 * 时间复杂度：$O(\log n)$。

typedef long long LL;
LL qmi(LL a, LL k, LL p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = (res * a) % p;
        a = (a * a) % p;
        k >>= 1;
    }
    return res;
}

5. 扩展欧几里得算法 (Extended Euclidean Algorithm)

作用

裴蜀定理告诉我们：对于任意正整数 $a, b$，必然存在整数 $x, y$，满足： $$ax + by = \gcd(a, b)$$ 扩展欧几里得算法不仅能求出 $\gcd(a, b)$，还能顺便求出方程中的一组解 $x$ 和 $y$。这在密码学（如计算乘法逆元、RSA 加密）中至关重要。

6. 中国剩余定理 (Chinese Remainder Theorem, CRT)

场景与公式

用来求解形如以下的同余方程组： $$\begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \dots \ x \equiv a_k \pmod{m_k} \end{cases}$$ （其中模数 $m_1, m_2, \dots, m_k$ 两两互质）。

构造法解题步骤

计算所有模数的乘积：$M = m_1 \cdot m_2 \cdots m_k$。
对于第 $i$ 个方程，计算 $M_i = \frac{M}{m_i}$。
求 $M_i$ 在模 $m_i$ 意义下的乘法逆元 $t_i$（满足 $M_i \cdot t_i \equiv 1 \pmod{m_i}$）。
方程组在模 $M$ 意义下的唯一解为： $$x = \sum_{i=1}^{k} a_i \cdot M_i \cdot t_i \pmod M$$

7. 高斯消元 (Gaussian Elimination)

作用

用来求解 $N$ 元一次方程组，或者求矩阵的秩、逆矩阵。

核心思想

利用初中学的“加减消元法”，把复杂的方程组通过行变换化简成阶梯型矩阵：

1x + 2y + 3z = 6
     0y + 4z = 4
          0z = 0  (无解或无数解)

最后从下往上“回代”求出每个未知数的值。

8. 求组合数 (Combinatorics)

概念

从 $a$ 个不同物品中选出 $b$ 个物品的方案数，记作 $C_a^b$ 或 $\binom{a}{b}$： $$\binom{a}{b} = \frac{a!}{b!(a-b)!}$$

不同情况下的求法

递推法（杨辉三角，适合数字较小）： $$\binom{a}{b} = \binom{a-1}{b-1} + \binom{a-1}{b}$$
费马小定理求逆元（适合 $a, b$ 很大，模数是质数）：把除法转换成乘法逆元：$\binom{a}{b} \equiv a! \cdot (b!)^{-1} \cdot ((a-b)!)^{-1} \pmod p$。
卢卡斯定理 (Lucas Theorem)：适合模数 $p$ 较小但 $a, b$ 极其巨大的情况。

9. 容斥原理 (Inclusion-Exclusion Principle)

核心思想

算几个集合的并集大小时，避免重复计算。 * 两个集合：$|A \cup B| = |A| + |B| - |A \cap B|$ * 三个集合： $$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$$ * 核心规律：“奇加偶减”——交集个数为奇数个集合的大小相加，交集个数为偶数个集合的大小相减。

10. 博弈论 (Game Theory)

两个经典博弈模型

巴什游戏 (Bash Game)：
一堆石子共 $n$ 个，两人轮流拿，每次最少拿 1 个，最多拿 $m$ 个，拿走最后一个的人赢。
结论：如果 $n$ 是 $(m+1)$ 的倍数，先手必输，否则先手必赢。
Nim 游戏：
有多堆石子，每次可以从任意一堆里拿任意个石子，最后拿光者胜。
结论：把所有堆的石子数量做异或和： $$S = a_1 \mathbin{\hat{}} a_2 \mathbin{\hat{}} \dots \mathbin{\hat{}} a_n$$ 如果 $S \neq 0$，先手必胜；如果 $S = 0$，先手必败。

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