1. 五级新增知识框架

• 初等数论：素数/合数、约数/倍数、GCD/LCM、同余、质因数分解、奇偶性。
• 欧几里得算法。
• 唯一分解定理。
• 埃氏筛、线性筛。
• 数组模拟高精度加减乘除。
• 单链表、双链表、循环链表。
• 二分查找、二分答案。
• 递归及复杂度。
• 分治：归并排序、快速排序。
• 贪心与最优子结构。

2. 初等数论核心表

概念	必背定义/公式
约数	若 $a\mid b$，则 a 是 b 的约数
倍数	若 $b=ka$，则 b 是 a 的倍数
素数	大于 1 且只有 1 和自身两个正约数
合数	大于 1 且不是素数
最大公约数	gcd(a,b)
同余	$a\equiv b\pmod m$ 表示 a,b 除以 m 余数相同
奇偶	偶数 $n\bmod2=0$；奇数 $n\bmod2=1$（对非负数理解）
最小公倍数

$$\operatorname{lcm}(a,b)=\frac{\left| ab \right|}{\gcd(a,b)}$$

|

3. 欧几里得算法

核心公式：$\gcd(a,b)=\gcd(b,a\bmod b)$。

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

时间复杂度通常为 $O(\log \min(a,b))$ 量级。

4. 唯一分解定理

每个大于 1 的整数都可唯一写成：

$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

其中 $p_i$ 为互不相同的素数，$a_i$ 为正整数；“唯一”忽略因子排列顺序。

试除分解复杂度

只需枚举到 $\sqrt n$：若 n 存在大于 $\sqrt n$ 的非平凡因子，则一定与一个小于 $\sqrt n$ 的因子配对。

5. 埃氏筛与线性筛

方法	核心思想	时间复杂度常见结论	特点
埃氏筛	从每个素数的倍数开始标记合数	$O(n\log\log n)$	简洁、常数小
线性筛	每个合数只由其最小质因子筛到一次	$O(n)$	可同时得到最小质因子等信息

埃氏筛骨架

vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; 1LL * i * i <= n; i++) {
    if (isPrime[i]) {
        for (long long j = 1LL * i * i; j <= n; j += i)
            isPrime[j] = false;
    }
}

6. 高精度运算

当整数超出 long long 范围时，可用数组/字符串逐位保存十进制数字。

运算	核心过程
加法	低位到高位逐位相加，carry = sum/10，当前位 sum%10
减法	低位到高位逐位相减，不够就借位
乘小整数	每位乘 b 再加进位
大整数乘法	位对位交叉相乘，累加到对应位置后统一进位
除小整数	高位到低位维护当前余数，逐位求商

建议记住：加减乘通常便于低位在前；除法通常按高位到低位处理。

7. 链表

单链表节点

struct Node {
    int val;
    Node *next;
};

双链表节点

struct Node {
    int val;
    Node *prev, *next;
};

链表	特点
单链表	只能顺着 next 向后
双链表	有 prev 与 next，可双向移动
循环链表	尾节点链接回首节点（或形成环）

操作复杂度

操作	已知目标位置/节点	需要从头查找
插入/删除	$O(1)$（指针已定位时）	$O(n)$ 查找 + 修改
按值查找	—	$O(n)$
随机访问第 k 个

与数组相比：链表随机访问差，但已定位节点的插删方便。

8. 二分查找

适用条件：答案空间或数组具有单调性。

有序数组找第一个 >= target

int l = 0, r = n; // 答案区间 [0,n]
while (l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] >= target) r = mid;
    else l = mid + 1;
}

时间复杂度：$O(\log n)$。

二分答案四问

1. 答案上下界是什么？
2. check(x) 表示什么？
3. check(x) 是否具有单调性？
4. 要找“最小可行”还是“最大可行”？

9. 递归

递归：函数直接或间接调用自身。

必须有：

1. 递归终止条件。
2. 规模缩小的递归调用。
3. 当前层与子问题答案的组合。

long long fac(int n) {
    if (n <= 1) return 1;
    return 1LL * n * fac(n - 1);
}

递归深度过大可能导致栈空间不足。

10. 分治

分治三步：

1. 分：将大问题拆成若干规模更小的同类问题。
2. 治：递归求解子问题。
3. 合：合并子问题答案。

归并排序

• 时间：$O(n\log n)$
• 额外空间：$O(n)$
• 稳定。

快速排序

• 平均时间：$O(n\log n)$
• 最坏时间：$O(n^2)$
• 原地实现通常额外空间较少（递归栈除外）。
• 通常不稳定。

11. 贪心

核心：每一步做当前看来最优的选择，希望组成全局最优。

贪心正确性常依赖：

• 贪心选择性质。
• 最优子结构。

典型模式：

问题	常见贪心策略
选最多不重叠区间	按结束时间从小到大选择
合并代价	每次取最小的若干项【视问题规则】
双指针配对	最轻与最重尝试配对

警告：局部最优并不总能推出全局最优，必须有问题结构保证。

12. 五级复杂度进阶

复杂度	增长速度直觉
$O(1)$	不随 n 增长
$O(\log n)$	每次规模成倍缩小
$O(n)$	扫一遍
$O(n\log n)$	高效排序/分治常见
$O(n^2)$	两层成比例循环
$O(2^n)$	枚举子集常见
$O(n!)$	枚举全排列常见

13. 五级必背易错点

1. 1 既不是素数也不是合数。
2. $\operatorname{lcm}$ 直接算 a*b 可能溢出，可先 a/gcd(a,b)*b。
3. 二分最难的是区间定义与更新方向，不是 mid 公式。
4. 递归必须保证规模真的缩小。
5. 快速排序最坏不是 $O(n\log n)$，而是 $O(n^2)$。
6. 链表不能像数组一样 $O(1)$ 随机访问。
7. 贪心策略必须证明/验证正确性。

14. 五级背诵清单

• [ ] GCD/LCM、同余、唯一分解定理。
• [ ] 埃氏筛与线性筛区别。
• [ ] 高精度四则运算逐位规则。
• [ ] 单/双/循环链表结构与复杂度。
• [ ] 二分查找和二分答案四问。
• [ ] 递归三要素。
• [ ] 归并/快排复杂度与稳定性。
• [ ] 贪心核心与适用前提。