算法竞赛常用数学符号与定义速查
引言
如果你曾经满怀信心地点开一篇题解,迎面撞上 a⊥b、⌊x⌋、(kn),然后默默把页面关掉——别难过,你不是一个人。
写下这篇速查的起因,是一个困扰了无数 OIer 的世纪难题:为什么题面和大佬题解里,这些符号总是约好了一样成群出现? 做题网站上它们满天飞:读题时它们静静躺在括号里,看题解时它们突然学会了一行表示一段话的压缩大法。每一个符号都在微笑着看你,仿佛在说:"这你都不懂?"
说实话,不懂太正常了。这些符号大多不是新的知识点,而是数学世界的"快捷键"——相当于 C++ 里的 using namespace std:没有它,代码照样能跑;有了它,确实优雅不少。唯一的问题是,第一次见到它们的人,都会怀疑自己打开的是不是天书。
所以这篇总结就诞生了,目的有两个:
- 查得懂:把这些散落在各大做题网站、题解区里的符号按类别收拢起来,每条附上含义、读法和 C++ 对照。以后读题面再遇到"熟人",直接翻到对应章节,三秒认亲。
- 有兴致:希望这份总结能顺手拉低一点数学的"恐怖指数"。很多符号背后其实是朴素得可爱的东西——a∣b 说白了就是"b 能被 a 整除",⌊x⌋ 就是"把 x 按到地上取整"。当你发现一个符号原来如此简单,数学在你心里大概也会从"天书"降级成"说明书"。
一、算术与数论
1.1 求和符号
$$\sum\_{i=1}^{n} a\_i = a\_1 + a\_2 + \cdots + a\_n$$
读作"从 i=1 到 n 对 a_i 求和"。∑ 是希腊字母 Sigma。
int sum = 0;
for (int i = 1; i <= n; ++i) sum += a[i];
常见变体:
| 写法 |
含义 |
等价代码 |
| ∑_i=1ni |
1+2+⋯+n |
n * (n + 1) / 2 |
| ∑_i∈Sa_i |
对集合 S 中所有下标求和 |
for (int i : S) sum += a[i] |
| $\sum\limits\_{i=1}^{n}\sum\limits\_{j=1}^{m} a\_{i,j}$ |
二重求和(先内后外) |
两层 for 循环 |
1.2 求积符号
$$\prod\_{i=1}^{n} a\_i = a\_1 \times a\_2 \times \cdots \times a\_n$$
读作"从 i=1 到 n 对 a_i 求积"。∏ 是希腊字母 Pi。
long long prod = 1;
for (int i = 1; i <= n; ++i) prod *= a[i];
1.3 阶乘
n!=1×2×3×⋯×n
特别规定 0!=1。n! 也是 ∏_i=1ni 的简写。
1.4 整除
a∣b
读作"a 整除 b",含义是 b 除以 a 的余数为 0,即 b=a⋅k 对某个整数 k 成立。
a∤b
读作"a 不整除 b"。
在代码中:
if (b % a == 0) // a 整除 b,即 a | b
常见混淆点:a∣b 和 a/b 完全不是一个意思。a∣b 是一个判断(是/否),a/b 是一个运算(得出商)。
1.5 取模与同余
取模运算:amodm 表示 a 除以 m 的非负余数,结果在 [0,m−1] 内。
int r = (a % m + m) % m; // 确保得到 [0, m-1] 的结果
C++ 中 % 对负数遵循"向零取整",所以 -7 % 5 结果为 -2。竞赛中几乎总是需要上面这种安全的写法。
同余:
a≡b(modm)
读作"a 与 b 模 m 同余"。这个关系有两种等价的表述方式:
- 用整除说:m∣(a−b),即 (a−b) 是 m 的倍数。
- 用余数说:a 和 b 除以 m 得到的余数相等。
注意区分:a≡b(modm)(两个数的关系)和 amodm(一个运算)。
1.6 最大公约数与最小公倍数
| 符号 |
含义 |
C++ |
| gcd(a,b) |
a 和 b 的最大公约数 |
gcd(a, b)(C++17 起在 <numeric>) |
| lcm(a,b) |
a 和 b 的最小公倍数 |
a / gcd(a, b) * b(防溢出写法) |
常用性质:
$$\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}, \qquad \gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b$$
1.7 互质
a 和 b 互质(也叫"互素"),指 gcd(a,b)=1。常记作 a⊥b。
提醒:⊥ 在几何里还表示"垂直"(AB⊥CD),两者全靠语境区分,详见七章。
1.8 数论函数
数论函数是以正整数为定义域的函数,在数论题(尤其莫比乌斯反演)中高频出现。常见几个:
| 符号 |
名称 |
含义 |
| φ(n) |
欧拉函数 |
1∼n 中与 n 互质的数的个数 |
| μ(n) |
莫比乌斯函数 |
n 含平方因子时为 0,否则为 (−1)k,k 为不同质因子个数 |
| τ(n) |
因子个数函数 |
n 的正因子个数 |
| σ(n) |
因子和函数 |
n 的所有正因子之和 |
| v_p(n) |
质因数指数 |
满足 pv_p(n)∣n 的最大非负整数 |
例如:φ(6)=2(1 和 5),τ(12)=6(因子 1,2,3,4,6,12),v_2(24)=3(24=23⋅3)。
读法:φ 读作 "phi"(费),μ 读作 "mu"(缪)。
1.9 对数
| 符号 |
读法 |
含义 |
| log_ab |
以 a 为底 b 的对数 |
满足 ax=b 的 x |
| log_2n |
以 2 为底的对数 |
复杂度中最常见,如 O(nlogn) |
| lnx |
自然对数 |
以 e≈2.718 为底 |
竞赛中"log"通常默认底数为 2,因为 O(logn) 描述的是"每轮规模减半"。C++ 中:
log2(n); // log_2(n)
log(n); // 自然对数 ln(n)
log10(n); // log_10(n)
1.10 幂与根
| 符号 |
读法 |
含义 |
| an |
a 的 n 次幂 |
n 个 a 相乘;特别地 a0=1 |
| a−n |
负指数 |
a−n=an1(a=0) |
| x |
根号 x |
x 的算术平方根,即满足 y2=x 的非负 y |
| nx |
n 次根号 |
满足 yn=x 的非负 y(n 为偶数时要求 x≥0) |
代码中 sqrt(x) 返回 double。对很大的整数开平方,浮点可能有精度问题,建议用 sqrtl(x) 或手写二分。
1.11 模逆元
若 gcd(a,m)=1,则 a 在模 m 下有逆元,记作 a−1,满足:
a⋅a−1≡1(modm)
竞赛中两种求法:m 为质数时用费马小定理 a−1≡am−2(modm)(快速幂);一般情形用扩展欧几里得解 ax≡1(modm)。
注意区分:a−1modm 是整数,不是小数 a1。出现分数取模(如 bamodm)时,写代码就是 a * inv(b) % m。
二、取整与近似
2.1 下取整
⌊x⌋
表示不大于 x 的最大整数,即"向下取整"。例如 ⌊3.7⌋=3,⌊−2.3⌋=−3。
在 C++ 中,整数除法自动向下取整(向零取整,对正数等价):
int a = 7 / 2; // 3,即 floor(3.5)
int b = -7 / 2; // -3(C++ 向零取整,不是数学意义上的 floor)
竞赛中经常需要数学意义的下取整(负数的 floor),如果需要严格行为,建议自己封装或用浮点 floor()。
2.2 上取整
⌈x⌉
表示不小于 x 的最小整数,即"向上取整"。例如 ⌈3.2⌉=4,⌈−2.3⌉=−2。
竞赛中最常用的整数上取整写法(正数):
int ceil_div = (a + b - 1) / b; // 计算 ceil(a / b),a, b 为正整数
2.3 约等于
a≈b
表示 a 约等于 b。竞赛中偶尔出现在浮点比较的题面中,代码里一般写为:
const double eps = 1e-9;
if (fabs(a - b) < eps) // a 和 b 在误差范围内视为相等
三、位运算
竞赛题面中,位运算通常用英文符号而非数学符号。但题解和推导中偶尔会出现数学记法。
3.1 按位与
按位与通常直接写 &,部分文献中用 ∧(逻辑与符号):
int c = a & b; // 按位与
常用技巧:x & 1 判断奇偶,x & (x - 1) 消去最低位的 1,x & (-x) 取出最低位的 1(lowbit)。
3.2 按位或
按位或通常写 |,部分文献中用 ∨:
int c = a | b; // 按位或
3.3 按位异或
按位异或通常写 ^,数学文献中常记为 ⊕:
int c = a ^ b; // 按位异或
⊕ 也在群论、线性基、Nim 博弈中出现。例如 Nim 和的记法:
G=a_1⊕a_2⊕⋯⊕a_n
3.4 按位取反
int c = ~a; // 按位取反
3.5 移位
| 符号 |
含义 |
C++ |
| a≪k |
a 左移 k 位,即 a×2k |
a << k |
| a≫k |
a 右移 k 位,即 ⌊a/2k⌋ |
a >> k |
四、集合与逻辑
4.1 集合
集合用花括号表示:
S={1,2,3,5,8}
空集记作 ∅ 或 ∅。
属于:x∈S 表示 x 是集合 S 的元素。
不属于:x∈/S。
代码中:
set<int> S = {1, 2, 3, 5, 8};
if (S.count(x)) // 等价于 x ∈ S
子集:A⊆B 表示 A 是 B 的子集(包含相等的情况)。
常用集合记法:
| 写法 |
含义 |
| {x∣P(x)} |
满足条件 P(x) 的所有 x 构成的集合 |
| {1,2,…,n} |
从 1 到 n 的所有整数 |
| Z |
整数集 |
| N |
自然数集(各文献对 0 是否属于有分歧) |
| R |
实数集 |
| [L,R] |
闭区间,包含两端点 |
| (L,R) |
开区间,不包含两端点 |
| [L,R) |
左闭右开,含左不含右(二分、双指针中常见) |
| (L,R] |
左开右闭,含右不含左 |
| Q |
有理数集 |
| C |
复数集 |
4.2 集合运算
| 符号 |
读法 |
含义 |
| A∩B |
A 交 B |
同时属于 A 和 B 的元素 |
| A∪B |
A 并 B |
属于 A 或属于 B 的元素 |
| A∖B |
A 减 B |
属于 A 但不属于 B 的元素 |
| A |
A 的补集 |
全集 U 中去掉 A 后剩下的元素 |
多重(大)交并:
$$\bigcap\_{i=1}^{n} S\_i, \qquad \bigcup\_{i=1}^{n} S\_i$$
读作"对 i 从 1 到 n 取交 / 取并"。容斥原理就建立在交并运算上。
4.3 逻辑量词与逻辑运算
量词:
| 符号 |
读法 |
含义 |
| ∀ |
"对任意" |
全称量词。∀x∈S 即"对 S 中的任意 x" |
| ∃ |
"存在" |
存在量词。∃x∈S 即"S 中存在某个 x" |
| ∄ |
"不存在" |
∄x 即 ¬(∃x) |
| ⟹ |
"推出" |
P⟹Q 即"若 P 则 Q" |
| ⟺ |
"等价于" |
P⟺Q 即"P 当且仅当 Q" |
逻辑运算:
| 符号 |
读法 |
含义 |
C++ |
| ¬P |
非 P |
P 的否定 |
!p |
| P∧Q |
P 且 Q |
P、Q 同时为真 |
p && q |
| P∨Q |
P 或 Q |
P、Q 至少一个为真 |
`p |
注意 ∧、∨ 也常在位运算文献中表示按位与、按位或(见 3.1、3.2),遇到时看上下文判断是"逻辑"还是"按位"。
4.4 势(集合大小)
∣S∣ 表示集合 S 中元素的个数。例如 ∣{2,3,5,7}∣=4。
int sz = S.size(); // |S|
五、组合数学
5.1 组合数
从 n 个不同元素中选出 k 个(无序)的方案数:
$$\binom{n}{k} = C(n, k) = \frac{n!}{k! \cdot (n-k)!}$$
读作"n 选 k"。(kn) 是最标准的数学写法,C_nk 在中文教材中也很常见。
5.2 排列数
从 n 个不同元素中选出 k 个并排列(有序)的方案数:
P(n,k)=A_nk=(n−k)!n!
5.3 二项式定理
$$(a + b)^n = \sum\_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$
六、其他常见符号
6.1 绝对值
∣x∣ 表示 x 的绝对值(模长)。代码中:
int abs_x = abs(x); // 整数
double abs_y = fabs(y); // 浮点数
6.2 不等于
a=b,代码中 a != b。
6.3 恒等
a≡b 在数论中常表示同余,在一般数学中表示"恒等于"(对所有变量取值都相等)。
6.4 函数映射
f:A→B 表示 f 是从集合 A 到集合 B 的一个函数(映射)。
6.5 无穷
∞ 表示无穷大。竞赛中通常在代码里用一个很大的常量表示"无限":
const int INF = 0x3f3f3f3f; // 约 10^9,适合做"无穷大"
const long long INF_LL = 1e18; // 更大范围的无穷
6.6 渐进复杂度记号
| 符号 |
含义 |
| O(f(n)) |
渐进上界。运算次数不超过 c⋅f(n)(n 充分大时) |
| Θ(f(n)) |
渐进紧界。运算次数恰好是 c_1⋅f(n) 到 c_2⋅f(n) 之间 |
| Ω(f(n)) |
渐进下界。运算次数至少为 c⋅f(n) |
竞赛中 O 最常见,通常用于描述算法复杂度,如 O(nlogn)、O(n2)。
6.7 概率与期望
| 符号 |
读法 |
含义 |
| P(A) |
A 的概率 |
事件 A 发生的概率,取值在 [0,1] |
| P(A∣B) |
条件概率 |
在 B 已发生的条件下,A 发生的概率 |
| E[X] |
期望 |
随机变量 X 的平均取值:E[X]=∑x_i⋅P(X=x_i) |
| xˉ |
x 拔 |
样本平均数:xˉ=nx_1+x_2+⋯+x_n |
| D(X) |
方差 |
衡量 X 的波动:D(X)=E[(X−E[X])2],也写作 Var(X) |
概率 DP、期望题中常见。代码里概率通常以"分数取模"出现,如 bamodm 写作 a * inv(b) % m。
6.8 最值与极值
| 符号 |
读法 |
含义 |
| max(a,b) |
取大 |
a、b 中的较大者 |
| min(a,b) |
取小 |
a、b 中的较小者 |
| max_ia_i |
求最大 |
所有 a_i 中的最大值 |
| argmax_xf(x) |
使最大的自变量 |
使 f(x) 取到最大值的那个 x |
代码中对应 std::max / std::min。argmax 在 DP 还原方案时常见——不只关心"最大是多少",还关心"在哪个位置取的"。
6.9 卷积
(f∗g)(n)=∑_if(i)⋅g(n−i)
读作"f 卷 g"。在多项式乘法、FFT / NTT、生成函数中高频出现。朴素实现是两层循环 O(n2),用 FFT 可优化到 O(nlogn)。
6.10 图论记号
| 符号 |
读法 |
含义 |
| G=(V,E) |
图 |
由点集 V 和边集 E 构成的图 |
| deg(v) |
度 |
点 v 的度数(相连的边数) |
| $ |
V |
、 |
无向图中 deg(v) 是连接 v 的边数;有向图区分入度 deg−(v) 和出度 deg+(v)。
6.11 矩阵记号
| 符号 |
读法 |
含义 |
| A_i,j |
A i j |
矩阵 A 第 i 行第 j 列的元素 |
| AT |
A 转置 |
转置矩阵,行列互换:(AT)_i,j=A_j,i |
| det(A) |
A 的行列式 |
方阵行列式,如 2×2 时 $\det \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc$ |
| A−1 |
A 的逆 |
满足 A⋅A−1=I 的矩阵(I 为单位阵) |
矩阵乘法、高斯消元、行列式、矩阵快速幂的题解里常见。
七、几何符号
几何题里偶尔会用到这些符号,量不大,但出现时往往决定你是否能读懂题意。
7.1 角度与三角形
| 符号 |
读法 |
含义 |
| ∠ABC |
角 |
以 B 为顶点的角 |
| △ABC |
三角形 |
由 A,B,C 三点构成的三角形 |
| π |
圆周率 |
常数,π≈3.14159,弧度制下平角为 π |
7.2 平行与垂直
| 符号 |
读法 |
含义 |
| a∥b |
平行 |
直线 a 与 b 平行 |
| AB⊥CD |
垂直 |
直线 AB 与 CD 垂直 |
重要提醒:⊥ 在数论里表示"互质"(a⊥b,见 1.7),在几何里表示"垂直"(AB⊥CD),两者毫无关系,全靠语境区分。
7.3 相似与全等
| 符号 |
读法 |
含义 |
| △ABC∼△DEF |
相似 |
形状相同、大小成比例 |
| △ABC≅△DEF |
全等 |
形状、大小完全相同 |
7.4 距离
d(A,B) 或 ∣AB∣ 表示点 A 到点 B 的距离。竞赛中常特指:
| 写法 |
含义 |
| $ |
x_1 - x_2 |
| (x_1−x_2)2+(y_1−y_2)2 |
欧几里得距离 |
7.5 向量运算
向量记作 a,其模长记作 ∣a∣。计算几何题解中两个核心运算:
| 符号 |
读法 |
含义 |
| a⋅b |
点积 |
$\vec{a} \cdot \vec{b} = |
| a×b |
叉积 |
二维下 a×b=x_1y_2−x_2y_1,正负判断点在线段的哪一侧 |
叉积的符号判断(左右关系)是计算几何所有凸包、凸多边形算法的基础。
八、速查总表
| 符号 |
读法 |
简要含义 |
| ∑ |
Sigma / 求和 |
累加 |
| ∏ |
Pi / 求积 |
累乘 |
| n! |
n 的阶乘 |
1×2×⋯×n |
| mod |
模 |
取余数 |
| ≡ |
同余 |
两数模 m 余数相同 |
| ∣ |
整除 |
a∣b 即 a 整除 b |
| ∤ |
不整除 |
a∤b 即 a 不整除 b |
| gcd |
最大公约数 |
gcd(a,b) |
| lcm |
最小公倍数 |
lcm(a,b) |
| φ(n) |
欧拉函数 |
1∼n 中与 n 互质的数的个数 |
| μ(n) |
莫比乌斯函数 |
含平方因子为 0,否则 (−1)k |
| τ(n) |
因子个数 |
n 的正因子个数 |
| σ(n) |
因子和 |
n 的正因子之和 |
| v_p(n) |
质因数指数 |
pv_p(n)∣n 的最大次数 |
| log_2n |
以 2 为底的对数 |
复杂度里的 log |
| lnx |
自然对数 |
以 e 为底 |
| ⊥ |
互质 / 垂直 |
数论中互质,几何中垂直(见七章) |
| ⌊x⌋ |
x 下取整 |
不大于 x 的最大整数 |
| ⌈x⌉ |
x 上取整 |
不小于 x 的最小整数 |
| ⊕ |
异或 |
按位异或,也用于 Nim 和 |
| ≪ |
左移 |
a≪k=a⋅2k |
| ≫ |
右移 |
a≫k=⌊a/2k⌋ |
| ∈ |
属于 |
x∈S |
| ∈/ |
不属于 |
x∈/S |
| ⊆ |
子集 |
A⊆B |
| ∅ |
空集 |
不含任何元素的集合 |
| ∩ |
交 |
A∩B:同时属于 A、B |
| ∪ |
并 |
A∪B:至少属于其一 |
| ∖ |
差 |
A∖B:属于 A 不属于 B |
| A |
A 的补集 |
全集中去掉 A |
| ∀ |
对任意 |
全称量词 |
| ∃ |
存在 |
存在量词 |
| ¬ |
非 |
逻辑否定 |
| ∧ |
且 |
逻辑与(也表按位与) |
| ∨ |
或 |
逻辑或(也表按位或) |
| [L,R) |
左闭右开 |
含左不含右 |
| (L,R] |
左开右闭 |
含右不含左 |
| $ |
S |
$ |
| (kn) |
n 选 k |
组合数 |
| an |
幂 |
n 个 a 相乘 |
| x |
根号 |
x 的算术平方根 |
| a−1 |
逆元 |
a⋅a−1≡1(modm) |
| P(A) |
概率 |
事件 A 发生的概率 |
| E[X] |
期望 |
随机变量 X 的平均取值 |
| xˉ |
x 拔 |
样本平均数 |
| D(X) |
方差 |
E[(X−E[X])2] |
| max / min |
最大 / 最小 |
取最值 |
| f∗g |
卷积 |
多项式乘法、FFT |
| a⋅b |
点积 |
判断夹角 |
| a×b |
叉积 |
判断左右关系 |
| G=(V,E) |
图 |
点集 V、边集 E |
| deg(v) |
度 |
点 v 的度数 |
| AT |
转置 |
行列互换 |
| det(A) |
行列式 |
方阵的行列式 |
| ∠ |
角 |
∠ABC |
| △ |
三角形 |
三点构成的图形 |
| ∥ |
平行 |
直线平行 |
| ∼ |
相似 |
形状相同 |
| ≅ |
全等 |
形状、大小都相同 |
| d(A,B) |
距离 |
点 A 到点 B 的距离 |
| ∞ |
无穷 |
无穷大 |
| O |
大 O |
渐进复杂度上界 |
九、许可协议
本文由 gakki 创作,采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际(CC BY-NC-SA 4.0) 许可证授权。
允许:复制、分发、展示、演绎(修改、再创作)本文。
前提是:
- 署名:转载或修改时须注明原作者与原始出处链接;
- 非商业性使用:不得将本文或其演绎作品用于商业目的(如售卖、付费课程等);
- 相同方式共享:基于本文创作的演绎作品,须以相同许可证发布。
完整法律文本见 CC BY-NC-SA 4.0 官方页面。