浅谈 CSP 数学知识点
weichenglu · · 算法·理论
浅谈 CSP 数学知识点
本篇文章耗时
板块一：数论基础
1、质数与合数
概念
-
质数（素数）：大于 1 的自然数，只有
1 和它本身两个因数。 -
合数：大于
1 且不是质数的自然数。 -
判定方法——试除法
检查从
这里便衍生出了通过代码判断质数的埃式筛和线性筛，这里不过多赘述（可以看这篇文章）
2、最大公约数（GCD）和最小公倍数（LCM）
概念
- 最大公约数：两个数中最大的公共因数。
- 最小公倍数：两个数中最小的公共倍数。
公式
求法——辗转相除法
也叫欧几里得算法。
反复用较大数除以较小数取余，直到余数为
当然，在代码中，求
3、分解质因数
概念
把一个合数写成几个质数相乘的形式。
方法——短除法
从最小质数
例题：分解 84
4、整除
概念
设
性质
- 如果
a\mid b 且b \mid c ，那么a \mid c -
a \mid b$ 且 $a\mid c$ 等价于对任意整数 $x$ 和 $y$，有 $a \mid (b\times x+c\times y) - 设
m \neq 0 ，那么a|b 等价于(m\times a)\mid(m \times b) - 设整数
x 和y 满足ax+by=1 ，且a\mid n 、b\mid n ，那么(a \times b) \mid n
证明：因为
再由性质
- 若
b=q\times d+c ，那么d\mid b 的充分条件是d\mid c 。
5、同余和模运算
概念
-
(a \times b) \bmod m = (a \bmod m \times b \bmod m) \bmod m
相关定理
- 威尔逊定理
若
- 费马小定理
若
- 欧拉定理
若
- 扩展欧拉定理
例题：计算 123 \times 456 \bmod 7
概念
所以，
8、扩展欧几里得 Exgcd (S 组)
用途
求方程
原理
与欧几里得算法（辗转相除法）相似的，已知
-
特殊地，若
b=0 ，则\gcd(a,0)=a 。此时取x=1，y=0 ，显然有a \cdot 1+0 \cdot 0=a 成立。 -
假设
b > 0 ，a \bmod b 通常可以写成a-b \cdot \lfloor \frac{a}{b} \rfloor 的形式，因此原方程可变化为：bx+(a-b \cdot \lfloor \frac{a}{b} \rfloor)y=\gcd(a,b) \Leftrightarrow ay+b(x-y \cdot \lfloor \frac{a}{b} \rfloor)=\gcd(a,b) 将
（3） 与原方程联立，因为各项系数相等，所以未知数相等，因此得：\begin{cases} x=y′ \\ y=x′-y′ \cdot \lfloor \frac{a}{b} \rfloor \end{cases} 按照这个规律，就可以写一个递归代码来解决问题了。
int x,y; void exgcd(int a,int b){ if (b == 0){ x = 1; y = 0; return; } else{ exgcd(b,a%b); int tmp = x; x = y; y = tmp - y*(a/b); } }
9、裴蜀定理 （S组）
基础定理
如果
换言之，若
推论
推论 1 （逆命题）：ax+by=1 有整数解时，当且仅当 \gcd(a,b)=1 ，即 a 与 b 互质。
推论 2 ：对于 n 个整数 a_1,a_2,\dots,a_n ，存在整数 x_1,x_2,\dots,x_n 使得 a_1x_1+a_2x_2+\dots+a_nx_n=\gcd(a_1,a_2,\dots,a_n)
模逆元
定义：对于整数
条件（重点）：
证明：
- 存在
x 使得ax \equiv 1 \pmod m - 设整数
y ，由上得ax-1=my ，这就等价于 存在整数x，y 使得ax+my=1 。 - 由裴蜀定理可得：
\gcd(a,m)=1 。
10、中国剩余定理 （S组）
概念
设
一定有整数解，并且在模
这里的”解唯一“的意思是：如果
求解方法——构造法
设：
-
M=m_1m_2\dots m_k - 对于每个
i ，令M_i = \frac{M}{m_i}
因为
然后可以构造：
(证明方法：将
最后，解为
例题
求解：
解：
-
M_1 = \frac{M}{m_1} = 35$，（求 $35 \pmod 3$ 的逆元，即解 $35x \equiv 1 \pmod 3$），所以 $t_1 = 2 -
M_2 = \frac{M}{m_2}=21$，逆元 $t_2=1 -
M_3= \frac{M}{m_3}=15$，逆元 $t_3 = 1
所以，
即，解为
扩展：模数不互质
方法：把两个同余方程合并成一个，减少方程数量，直到只剩一个。
- 判断方程是否有解：对于
\begin{cases} x \equiv a \pmod {m} \\ x \equiv b \pmod {n} \end{cases} 有解得条件是满足a \equiv b \pmod {\gcd(m,n)} 。
原因：设任意整数
- 由上
mk \equiv b-a \pmod n ，设d=\gcd(m,n) ，令原同余方程两边除以d ，\frac{m}{d} \times k \equiv \frac{b-a}{d} \pmod {\frac{n}{d}} 。 - 此时，有
\gcd(\frac{m}{d},\frac{n}{d}) = 1 ，所以，\frac{m}{d} 在模\frac{n}{d} 有逆元。 - 两边同时乘以逆元，解出
k \equiv k_0 \pmod {\frac{n}{d}} ，其中k_0 = (\frac{m}{d})^{-1} \times \frac{b-a}{d} \pmod {\frac{n}{d}} 。 - 因此，
k=k_0+\frac {n}{d} \times t ，代回x=a+mk ，得x=a+mk_0+\frac{nm}{d}\times t 。 - 合并后的模数是
\operatorname{lcm}(n,m) = \frac{nm}{d} ，因此x \equiv a+mk_0 \pmod {\operatorname{lcm}(n,m)} 。
例题 1 ：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷
#include <bits/stdc++.h>
#define int __int128
#define N 15
using namespace std;
long long n;
long long a[N],b[N];
int m[N];
int M;
int ans;
int x,y;
void exgcd(int u,int v){
if (v == 0){
x = 1;
y = 0;
return;
}
exgcd(v,u%v);
int temp = x;
x = y;
y = temp - y*(u/v);
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1;i<=n;++i) cin >> a[i] >> b[i];
M = 1;
for (int i=1;i<=n;++i) M *= a[i];
for (int i=1;i<=n;++i) m[i] = M / a[i];
for (int i=1;i<=n;++i){
exgcd(m[i],a[i]);
x = (x + a[i]) % a[i]; //先求最小解！！！
ans = (ans + b[i] * m[i] * x + M) % M;
}
cout << (long long)ans;
return 0;
}例题 2 ：P4777 【模板】扩展中国剩余定理（EXCRT） - 洛谷
#include <bits/stdc++.h>
#define int __int128
#define N 100005
using namespace std;
long long n;
long long a[N],b[N];
int x,y;
int A,B;
int t;
void exgcd(int u,int v){
if (v == 0){
x = 1;
y = 0;
t = u;
return;
}
exgcd(v,u%v);
int temp = x;
x = y;
y = temp - y * (u/v);
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
A = 1;
for (int i=1;i<=n;++i) cin >> a[i] >> b[i];
for (int i=1;i<=n;++i){
exgcd(A,a[i]);
x = (B - b[i]) / t * x;
B = B - A * x;
A = a[i] / t * A;
B = (B+A)%A;
}
cout << (long long)((B+A)%A);
return 0;
}11、斐波那契数列
定义
性质
（1）卡西尼性质：
（2）附加性质：
（3）在上一性质中，当
（4）由上一性质可以归纳证明：
（5）上一条性质可逆，即：
（6）
（7）
（8）
（9）
通项公式
板块二：计数原理
1、集合基本概念
- 集合：由确定的、互不相同的对象组成的整体。
- 元素：集合中的每个对象。
- 空集
∅ ：不含任何元素的集合。 - 全集
U ：研究范围内所有元素的集合。 - 子集：若
A 的所有元素都在B 中，则记作A \subseteq B 。 - 真子集：若
A \subseteq B 且A \neq B ，记A \subset B 。
规律：含
2、集合的基本运算
| 运算 | 符号 | 含义 | 记法 |
|---|---|---|---|
| 并集 | 属于 |
||
| 交集 | 同时属于 |
||
| 补集 | 全集中不属于 |
||
| 差集 | 属于 |
||
| 对称差 | 属于 |
3、加法原理
概念：完成一件事有
关键词：“要么……要么……”、分类、或等
易错：各类必须互斥，否则需用容斥原理修正。
4、乘法原理
概念：完成一件事需
关键词：“先……再……”、分步、且等
易错：每一步方法数必须固定不变（不能受之前影响）。若某一步受前一步影响，则不能直接相乘，要分类讨论。
5、抽屉原理
概念：把
6、容斥原理
这个计数原理及其重要，前面几个小学的时候就都学过，但是容斥原理在小学应该也只是初步学习而已。
二集合公式：
三集合公式：
对此，进行一个推广：设满足属性
根据容斥原理，有：
拿全集
通俗地讲：奇数个条件，做减法；偶数个条件，做加法。（不会也没关系）
板块三：排列组合
1、排列数 A(n,m)
概念
从
公式
2、组合数 C(n,m)
概念
从
公式
性质
-
C^n_m=C^{n-m}_m$，并且规定：$C^0_n=1$，$C^n_n = 1 -
C^m_{n+1}=C^m_n+C^{m-1}_n
可重复组合
概念：从
公式：组合数记为
3、捆绑法（相邻问题）
用处：几个元素必须排在一起 。
步骤
- 把必须相邻的元素绑成一个 “大元素”，即把他捆起来当做一个元素处理。
- 先排列所有“大元素”和其他元素。
- 再乘 “大元素” 内部的排列数。
4、插空法（不相邻问题）
用处：几个元素不能相邻。
步骤
- 先排其他元素，产生若干个空位。（包括两端）
- 把不相邻的元素插入空位。
5、隔板法（相同物品分配）
用处：把
步骤
- 不允许空盒：
C(n-1,k-1) - 允许空盒：
C(n+k-1,k-1)
技巧：用 先每人给1个 将 不允许空盒 转化为 允许空盒。
6、环形排列
公式：
7、错排问题（S组）
概念：
公式：
边界：
8、卡特兰数（S组）
是一个计数问题的经典数列，前几项为：
公式
-
递归公式
1 f(n)=\sum^{n-1}_{i=0} f(i) \times f(n-i-1) -
递归公式
2
- 组合公式
1
- 组合公式
2
应用场景：
9、第二类斯特林数
概念
把
递推公式
边界：
考虑最后一个球，若它单独放一个盒子，有
板块四：概率论基础
1、事件与概率
随机试验、样本空间和样本点
在相同条件下可以重复进行；每次试验的可能结果可以不止一个，并能事先明确试验的所有可能结果；结果不确定的试验。
随机试验所有可能结果的集合，叫做样本空间，一般记为
事件
- 事件：
S （样本空间） 的子集，称为随机事件，简称事件。 - 发生：在每次试验中，当且仅当这一子集中的一个样本点出现时，称这一事件发生。
- 基本事件：由一个样本点组成的单个元素的集合。
- 必然事件：
S 是自身的一个子集，在每次试验中它是必然发生。 - 不可能事件：每次试验中都不可能发生的事件，即：空集 ∅。
事件关系与运算
当有多个事件时，可以表示成
当有多个事件时，可以表示成
频率与概率
频率：如果在相同的条件下进行了
概率：在大量进行同一重复试验时，事件
概率的性质（S组）：
- 非负性：
0 \leq P(A) \leq 1 - 规范性：对于必然事件
A ，P(A) = 1 ；对于不可能事件A （空集），P(A)=0 - 容斥性：对于任意两个事件
A 和B ，P(A \cup B)=P(A)+P(B)-P(A \cap B) - 互斥事件的可加性：若事件
A_1,A_2,\dots,A_n 互斥，则P(\cup^n_{i=1} A_i)=\sum^n_{i=1} P(A_i) - 独立事件的可乘性：若事件
A_1,A_2,\dots,A_n 相互独立，则P(\cap^n_{i=1} A_i)=\prod^n_{i=1} P(A_i)
2、古典概率
定义
如果某次试验满足：
- 有限性：样本空间只有有限个样本点。
- 等可能性：试验中每个结果出现的可能性相同。
- 这些随机现象所能发生的事件互不相容。
则称该试验为古典概型，计算古典概型的方法称为古典概率。事件
3、数学期望（S组）
期望定义
举个例子：我们来玩一个游戏，如果有
分析这个例子，抽中的概率是
对于离散型变量
联系一下其他知识，公式里的
期望性质
- 线性性质：
E(aX+bY)=a \cdot E(X)+b \cdot E(Y) ，另外地，若X 与Y 独立，有E(XY)=E(X) \cdot E(Y) - 全概率公式：
P(A)=\sum_{i=1}^n P(A\mid B_i)\cdot P(B_i)=\sum_{i=1}^n (A \cap B_i)
总结
就讲到这吧，应该已经够用了。初赛最为重要的其实还是排列组合和一些简单的数论知识，像期望这一些东西作者并没有在初赛试题中见到很多。
参考文章
浅谈拓展欧几里得算法（Exgcd） - 洛谷专栏