2026 信奥赛 CSP-J 必备数学知识点汇总

数论

基础数论

整数奇偶性

判断 n 是否为奇数：
if (n % 2 != 0) { ... } // 或位运算 if (n & 1) { ... }
约数与倍数

最大公约数 (GCD)：
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
最小公倍数 (LCM)：
int lcm(int a, int b) { return a / gcd(a, b) * b; }
平均数

算术平均数 = 总和 / 个数

double avg = (double)sum / count;
同余、模运算

模运算的基本性质：

// 防止溢出的加法和乘法 long long add(long long a, long long b, long long p) { return (a % p + b % p) % p; } long long mul(long long a, long long b, long long p) { return ((a % p) * (b % p)) % p; }
质数与合数

判断质数 (O(√n))：
bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; }
分解质因数

for (int i = 2; i * i <= n; i++) { while (n % i == 0) { // i 是质因数 n /= i; } } if (n > 1) // 剩下的 n 也是质因数
周期问题

寻找序列的循环节。例如：今天是星期一，100天后是星期几？

int day = (1 + 100) % 7; // 注意处理余数为0的情况（视具体问题而定）
整式的认识

单项式：数与字母的积。

多项式：几个单项式的和。

// 多项式通常用数组表示系数 // P(x) = 2x^2 + 3x + 1 int p[3] = {1, 3, 2}; // p[i] 表示 x^i 的系数
等式与一元一次方程

形如 ax + b = 0 的方程。

int x = -b / a; // 需注意 a != 0
二元一次方程

通用形式：ax + by = c; dx + ey = f

使用克莱姆法则或代入消元求解。

// 简单代入消元思想 // 若 y = (c - ax) / b // 代入第二个方程求解 x
数列问题

等差数列求和：Sn = n(a1 + an) / 2

等比数列求和：Sn = a1(1 - q^n) / (1 - q)

// 等差数列求和 long long sum = (long long)n * (a1 + an) / 2;

计算

高精度计算

竖式计算

使用数组模拟手工加减乘除。
// A + B 核心逻辑 for (int i = 0; i < len; i++) { c[i] += a[i] + b[i]; c[i+1] = c[i] / 10; c[i] %= 10; }

图形

几何基础

几何图形

三角形三边关系：两边之和大于第三边。

// 判断能否构成三角形 if (a + b > c && a + c > b && b + c > a) { cout << "Yes"; }
周长面积

长方形：C=2(a+b), S=ab

圆形：C=2πr, S=πr²

const double PI = 3.1415926535; double area = PI * r * r; double circ = 2 * PI * r;
平面直角坐标

两点间距离公式：

double dist = sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));

中点公式：x = (x1+x2)/2, y = (y1+y2)/2

枚举

基础算法

暴力求解

列举所有可能的情况。
// 百钱买百鸡 for (int x = 0; x <= 20; x++) for (int y = 0; y <= 33; y++) { int z = 100 - x - y; if (z%3==0 && 5*x+3*y+z/3==100) ... }

组合

组合数学

排列组合

组合数性质：C(n,m) = C(n, n-m)

// 杨辉三角递推求组合数 c[0][0] = 1; for(int i=1; i<=n; i++) { c[i][0] = 1; for(int j=1; j<=i; j++) c[i][j] = c[i-1][j] + c[i-1][j-1]; }

数组

二维与多维数组

矩阵、行列式

// 遍历二维数组 for(int i=0; i> a[i][j];

矩阵加法：对应位置元素相加。

矩阵乘法：C[i][j] = Σ(A[i][k] * B[k][j])

二分

分治思想

数学二分法

查找 x 在有序数组 a 中的位置：
int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (a[mid] == x) return mid; else if (a[mid] < x) l = mid + 1; else r = mid - 1; }

贪心

最优解问题

一次函数最值

y = kx + b (k ≠ 0)

单调性决定最值位置。

// 区间 [L, R] 上的最值 if (k > 0) max_val = k * R + b; else max_val = k * L + b;
二次函数最值

y = ax² + bx + c (a ≠ 0)

// 对称轴 double axis = -b / (2.0 * a); // 顶点纵坐标 (4ac - b^2) / 4a double vertex_y = (4*a*c - b*b) / (4.0*a);
线段最值

活动选择问题（区间调度）：

// 按结束时间排序 sort(a, a+n, cmp_end_time); int count = 1, last_end = a[0].end; for(int i=1; i= last_end) { count++; last_end = a[i].end; } }
面积最值

周长固定的矩形，正方形面积最大。

// a + b = C/2 (定值) // ab <= ((a+b)/2)^2 // 当且仅当 a=b 时取等号

模拟

基础逻辑

数学归纳法

第一步 (奠基)：证明 n=1 成立。

第二步 (归纳)：假设 n=k 成立，推导 n=k+1 成立。

// 递归思想与数学归纳法类似 void solve(int n) { if (n == 1) { ...; return; } solve(n-1); // 由 n-1 的解推导 n 的解 }
递归

函数自己调用自己。

// 阶乘 int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); }

动态规划

简单 DP

函数

状态转移方程是 DP 的核心。

// 斐波那契数列 DP int f[100]; f[1] = f[2] = 1; for(int i=3; i<=n; i++) { f[i] = f[i-1] + f[i-2]; }
对数函数

y = logₐx

#include <cmath> // 以 e 为底 double v1 = log(x); // 以 10 为底 double v2 = log10(x); // 以 2 为底 double v3 = log2(x);

集合

集合论

集合、交并补

容斥原理：|A ∪ B| = |A| + |B| - |A ∩ B|

#include <set> set<int> s; s.insert(1); if (s.count(1)) { ... } // 检查元素是否存在

图论

图结构

最短路径思想

Dijkstra 适用于非负权图。

// Floyd 算法核心 for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

数据结构

队列、栈、搜索

数据结构与搜索

栈 (Stack): 先进后出 (LIFO)。

队列 (Queue): 先进先出 (FIFO)。

stack<int> s; s.push(1); s.pop(); queue<int> q; q.push(1); q.pop();