当前位置：首页 > news >正文

OI 数学定理（提高级）

news 2025/10/1 6:52:02

持续更新中……

数论和线性代数

初等数论是数学的一个分支，这里将列出算法竞赛中常用的初等数论问题和线性代数问题。

质数与约数

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)$：

\[\varepsilon(n)=\begin{cases} 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)$。

6. 唯一分解定理

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

7. 莫比乌斯函数的定义

\[\mu(n)=\begin{cases} 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$。

$(p-1)!\equiv -1(\text{mod}\space p)$ 是 $p$ 为质数的充分必要条件。

不定方程

二元线性丢番图方程

二元线性丢番图方程 $ax+by=c$。（$a,b,c$ 是已知整数，$x,y$ 是变量，问是否有整数解）

扩展欧几里得算法

问题：求 $ax+by=\gcd(a,b)$ 的一组整数解。

离散与组合数学

组合数求解

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_p^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$ 中的元素都不相同，组合数：

\[C^r_n =\begin{pmatrix} n\\ r \end{pmatrix} = \frac{P_p^r}{r!} = \frac{n!}{r!\cdot (n-r)!} \]

4. 组合数的性质

$C^r_n=C^{n-r}_n$；
$C^r_n=C^r_{n-1}+C^{r-1}_{n-1}$；
$C^0_n+C^1_n+C^2_n+C^n_n = 2^n$；

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

$S$ 中的元素可以相同，称多重集，如：$S=\{5\times a,7\times b,4\times c\}$。

无限多重集的排列
- $S$ 是一个多重集，它有 $k$ 个不同的元素，每个元素都有无穷重复个数，$S$ 的 $r$ 排列个数为 $k^r$。
有限多重集的排列
- $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!}$
有限多重集的组合
- $S$ 是一个多重集，它有 $k$ 个不同的元素，每个元素都有无穷重复个数，那么 $S$ 的 $r$ 组合的个数为：

\[C^{r}_{r+k-1}=\begin{pmatrix} 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) \]

9. 鸽巢原理

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

容斥原理和卡特兰数

容斥原理

设 $A$、$B$ 是分别具有性质 $P_1$ 和 $P_2$ 的有限集，则有：$|A\cup B| =|A|+|B|-|A\cap B|$。
【集合的交等于全集减去补集的并】设 $U$ 中元素有 $n$ 种不同的属性，那么第 $i$ 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成集合 $S_i$，那么：