OI 数学定理（提高级）

Lonely_Peak · 2025-07-24 18:06:36 · 算法·理论

这里整理了在 CCF CSP-S 中可能会用到的数学定义与定理，希望对备战 CSP-S 的选手有所帮助。

数论和线性代数

质数与约数

1. 算数基本定理

每个数都能唯一的表示成它的质因数的乘积。

n=p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_s^{a_s},p_1<p_2<p_3<\cdots<p_s

2. 约数

N=\prod_{i=1}^{k} p_i^{a_i} = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}

约数个数：\prod_{i=1}^{k}(a_i + 1)=(a_1 +1)(a_2+1)\cdots(a_k+1)
约数之和：

\prod_{i=1}^{k} \sum_{j=0}^{a_i} p_i^j = (p_1^0+p_1^1+\cdots+p_1^{a_1})(p_2^0+p_2^1+\cdots+p_2^{a_2})\cdots(p_k^0+p_k^1+\cdots+p_k^{a_k})

3. 积性函数

定义在所有正整数上的函数称为算术函数。如果算术函数 f 对任意两个互素的正整数 p 和 q，均有：

f(pq)=f(p)f(q)

如果对任意两个正整数 p 和 q，均有 f(pq)=f(p)f(q)，称为完全积性函数。

积性函数的和函数也是积性函数。如果 f 是积性函数，那么 f 的和函数 F(n)=\sum_{d|n} f(d) 也是积性函数。

4.常见积性函数

恒等函数 I(n)： I(n)=n
单位函数 id(n)： id(n)=n
幂函数 I_k(n)： I_k(n)=n^k
元函数 \varepsilon(n)：

1,&n=1\\ 0,&n>1 \end{cases}

因子和函数 \sigma(n)： \sigma(n)=\sum_{d|n} d
约数个数 d(n)： d(n)=\sum_{d|n} 1

5. 欧拉函数

设 n 是一个正整数，欧拉函数 \varphi(n) 定义为不超过 n 且与 n 互素的正整数的个数。定理：设 p 和 q 是互素的正整数，那么 \varphi(pq)=\varphi(p)\varphi(q)。

若 p 是质数，则 \varphi(p)=p-1。
若 p 是质数，则 \varphi(p^k)=(p-1)p^{k-1}。
积性函数：若 \gcd(m,n)=1，则 \varphi(mn)=\varphi(m)\varphi(n)。

计算方法：

\varphi(n) = \prod_{i=1}^{r} p_i^{k_i-1}(p_i-1) = \prod_{p|n} p^{\alpha_p-1} (p-1) = n \prod_{p|n} \frac{p-1}{p}

6. 唯一分解定理

n=\prod_{i=1}^{s} p_i^{a_i}

7. 莫比乌斯函数的定义

1&n=1\\ 0&n 含相同质因子\\ (-1)^s& s为n的质因子个数 \end{cases}

8. 欧拉定理

对于整数 a 和正整数 m，如果 a 和 m 互质，即 \gcd(a,m)=1，则 a^{\varphi(m)} \equiv 1 (\text{mod} \space m)。

裴蜀定理与同余式

1. 最大公因数

\gcd(a,b) = \gcd(a,a+b) = \gcd(a,k\cdot a+b)
\gcd(ka,kb)=k\cdot \gcd(a,b)
若 \gcd(a,b)=d，则 \gcd(\frac{a}{d},\frac{b}{d})=1，即 \frac{a}{d} 与 \frac{b}{d} 互质。
\gcd(a+cb,b)=\gcd(a,b)
2. 最小公倍数
\text{lcm}(a, b) = a\times b\div \gcd(a, b) = a\div\gcd(a, b)\times b
3. 裴蜀定理

对于整数 a，b，设 d=\gcd(a,b)，对于整数 m，方程 ax+by=m 有解当且仅当 m 是 d 的倍数。特别的，ax+by=1 有解当且仅当 a 与 b 互质。（如果 a 与 b 均为整数，则有整数 x 和 y 使得 ax + by = \gcd(a, b)）

4. 模运算的性质

加：(a+b) \mod m = [(a \mod m) + (b \mod m)] \mod m
减：(a-b) \mod m = [(a \mod m) - (b \mod m)] \mod m
乘：(a\times b) \mod m = [(a \mod m) \times (b \mod m)] \mod m

5. 同余

设 m 是正整数，若 a 和 b 是整数，且 m | (a - b)，则称 a 和 b 模 m 同余。a 除以 m 得到的余数，和 b 除以 m 的余数相同；或者说，a - b 除以 m，余数是 0。

把 a 和 b 模 m 同余记为 a\equiv b (\text{mod}\space m)，m 称为同余的模。

6. 逆

给定整数 a，且满足 \gcd(a, m) = 1，称 ax\equiv 1(\text{mod}\space m) 的一个解为 a 模 m 的逆。记为 a^{-1}。

7. 逆与除法取模

设 b 的逆元是 b^{-1}，有：

(a\div b)\mod m = [(a\div b)\mod m][(bb^{-1})\mod m]=(a\div b \times bb^{-1}) \mod m = (ab^{-1})\mod m

经过上述推导，除法的模运算转换为乘法模运算，即：

(a\div b)\mod m = (ab^{-1})\mod m = (a\mod m)(b^{-1} \mod m) \mod m

8. 威尔逊定理

若 p 为素数，则 p 可以整除 (p - 1)! + 1。

不定方程与同余方程

1. 二元线性丢番图方程

二元线性丢番图方程 ax+by=c。（a,b,c 是已知整数，x,y 是变量，问是否有整数解）ax + by = c 有解的充分必要条件是 d = \gcd(a, b) 能整除 c。
设 a，b 是整数且 \gcd(a, b) = d。
- 如果 d 不能整除 c，方程 ax + by = c 没有整数解
- 如果 d 能整除 c，那么存在无穷多个整数解。
- 如果 (x_0，y_0) 是方程的一个特解，通解：\ $y = y_0 - (a\div d)n$ 其中 $n$ 是任意整数。

2. 扩展欧几里得算法与二元丢番图方程的解

判断方程 ax + by = c 是否有整数解，即 \gcd(a,b) 能整除 c。记 d = \gcd(a,b)。
方程 ax + by = c 的通解：x = x_0' + (b\div d)n，y = y_0' - (a\div d)n

3. 一元线性同余方程

设 x 是未知数，给定 a、b、m，求整数 x，满足 ax \equiv b (\text{mod}\space m)。
求解一元线性同余方程等价于求解二元线性丢番图方程。

4. 中国剩余定理

x \equiv a_1 (\text{mod}\space m_1)\\ x \equiv a_2 (\text{mod}\space m_2)\\ \cdots\\ x \equiv a_n (\text{mod}\space m_n) \end{cases}

对于上述方程，若 m_1,m_2,\cdots,m_3 两两互质，则在模 M=m_1 m_2\cdots m_n 下，方程仅有一个解。令 M_i=\frac{M}{m_i}，v_i\equiv M_i^{-1} (\text{mod}\space m_i) 则方程解为：

x\equiv a_1 M_1 v_1 + a_2 M_2 v_2 +\cdots + a_n M_n v_n

x=\sum_{i=1}^{n} r_i c_i c_i^{-1} (\text{mod}\space M)

5. 扩展中国剩余定理

x \equiv a_1 (\text{mod}\space m_1)\\ x \equiv a_2 (\text{mod}\space m_2)\\ \cdots\\ x \equiv a_n (\text{mod}\space m_n) \end{cases}

对于上述方程，m_1,m_2,\cdots,m_3 为不一定两两互质的整数。

其特解：p=p\times \frac{r_2-r_1}{\gcd},q=q\times \frac{r_2-r_1}{\gcd}。
其通解：P=p+\frac{m_2}{\gcd}\times k, Q=q-\frac{m_1}{\gcd}\times k。
所以：x=m_1 P + r_1 = \frac{m_1 m_2}{\gcd} \times k +m_1 p+r_1

离散与组合数学

组合数求解

1. 加法原理和乘法原理

加法原理：设集合 S 划分为部分 S_1,S_2,\cdots,S_m，则 S 的元素个数可以通过每一部分的个数来确定，即 |S|=|S_1|+|S_2|+\cdots+|S_m|。
乘法原理：令 S 是元素的序偶 (a,b) 的集合

2. 排列
不可重复排列（从 n 个不同的物品中不重复的取出 r 个），排列数为：
P_n^r = n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}
可重复排列（从 n 个不同的物品中可重复的取出 r 个），排列数为：n^r。
圆排列（从 n 个元素中选 r 个圆排列），排列数为：\Large \frac{P^r_n}{r}=\frac{n!}{r(n-r)!}

3. 组合

如果 S 中的元素都不相同，组合数：

n\\ r \end{pmatrix} = \frac{P_n^r}{r!} = \frac{n!}{r!\cdot (n-r)!}

4. 组合数的性质

5. 多重集合的排列和组合

1. 无限多重集的排列 - $S$ 是一个多重集，它有 $k$ 个不同的元素，每个元素都有无穷重复个数，$S$ 的 $r$ 排列个数为 $k^r$。 2. 有限多重集的排列 - $S$ 是一个多重集，它有 $k$ 个不同的元素，每个元素的重数分别为 $n_1, n_2, \cdots, n_k$，$S$ 的大小是 $n = n_1+ n_2 + \cdots + n_k$，则 $S$ 的 $n$ 排列个数为：$\large \frac{n!}{n_1!n_2!\cdots n_k!}

有限多重集的组合

r+k-1\\ r \end{pmatrix}=C^{k-1}_{r+k-1}=\begin{pmatrix} r+k-1\\ k-1 \end{pmatrix}

6. 杨辉三角计算公式

组合公式 C_n^r=\begin{pmatrix}n\\r\end{pmatrix} = \frac{n!}{r!\cdot (n-r)!}，把 C_n^r 称为二项式系数。杨辉三角是二项式系数的典型应用。
杨辉三角可以用 (x+1)^n 来定义和计算。

7. 二项式定理

组合公式 C^r_n =\begin{pmatrix}n\\r\end{pmatrix} = \frac{n!}{r!\cdot (n-r)!}，就是 (x+1)^n 展开后第 r 项的系数。 (x+1)^n=\sum_{r=0}^{n} C^r_n x^r
推导得到二项式定理： (a+b)^n = \sum_{r=0}^{n} C_n^r a^r b^{n-r} = \sum_{r=0}^{n} C_n^r b^r a^{n-r}
二项式系数的两种计算方法：
1. 递推公式：C_n^r = C_{n-1}^r + C_{n-1}^{r-1}；
2. 用逆直接计算： C_n^r \mod m = \frac{n!}{r! (n-r)!} \mod m = (n! \mod m)[(r!)^{-1} \mod m]\{[(n-r)!]^{-1} \mod m\} \mod m

8. 卢卡斯定理

对于非负整数 n、r 和素数 m，有： C_n^r \equiv \prod_{i=0}^{k} C_{n_i}^{r_i} (\text{mod}\space m) C_n^r \mod m = C_{n\mod m}^{r\mod m} \times C^{\frac{r}{m}}_{\frac{n}{m}} \mod m

9. 鸽巢原理

推广：k\times n+1只鸽子住 n 个巢里，那么至少有一个巢里有 k+1 只或更多鸽子。

容斥原理和卡特兰数

1. 容斥原理

设 A、B 是分别具有性质 P_1 和 P_2 的有限集，则有：|A\cup B| =|A|+|B|-|A\cap B|。
【集合的并等于集合的交的交错和】设 U 中元素有 n 种不同的属性，那么第 i 种属性称为 P_i，拥有属性 P_i 的元素构成集合 S_i，那么：
\Bigg| \bigcup_{i=1}^{n} S_i \Bigg| = \sum_{m-1}^{n} (-1)^{m-1} \sum_{a_i<a_{i+1}} \Bigg| \bigcap_{i=1}^{m} S_{a_i} \Bigg|
【集合的交等于全集减去补集的并】设 U 中元素有 n 种不同的属性，那么第 i 种属性称为 P_i，拥有属性 P_i 的元素构成集合 S_i，那么：
\Bigg| \bigcap_{i=1}^{n} S_i\Bigg| = |U| - \Bigg| \bigcup_{i=1}^{n} \overline{S_i}\Bigg|

2. Catalan 数

Catalan 数是一个数列，它的一种定义是： C_n = \frac{1}{n+1} \begin{pmatrix} 2n \\ n \end{pmatrix} , \space n=0,1,2,\cdots
通项公式：