这里整理了在 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

。

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

不定方程与同余方程

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)$ 是方程的一个特解，通解：
  $x = x_0 + (b\div d)n$
  $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. 扩展中国剩余定理 $$\begin{cases} 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$ 中的元素都不相同，组合数： $$C^r_n =\begin{pmatrix} n\\ r \end{pmatrix} = \frac{P_n^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+ \cdots +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$ 组合的个数为：

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$
通项公式：
1. $H_n=C^n_{2n}-C^{n-1}_{2n}$ ；
2. $H_n=\frac{1}{n+1} C^n_{2n}$ ；
3. $H_n=\frac{4n-2}{n+1} H_{n-1}$ ；

OI 数学定理（提高级）

文章操作