知识块①：初等数论
·1.1 素数与合数
素数（质数）：大于1的自然数中，除了1和它本身以外不再有其他因数。如：2, 3, 5, 7, 11...
合数：大于1的自然数中，除了1和它本身以外还有其他因数。如：4, 6, 8, 9, 10...
判断一个数是否为素数——枚举到√n：
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) // 注意：是 i*i <= n，不是 i*i < n
if (n % i == 0) return false;
return true;
}
（2024年3月第9题：循环条件应该是 i*i <= n 还是 i*i < n？答案是 <=）
为什么只需要检查到√n？ 如果n有大于√n的因子a，那么n/a一定小于√n，所以只需要检查到√n即可。
·1.2 最大公约数与最小公倍数
最大公约数： 两个或多个整数共有的约数中最大的那个。记为 gcd(a, b)。
最小公倍数： 两个或多个整数共有的倍数中最小的那个。记为 lcm(a, b)。
关系公式：gcd(a, b) × lcm(a, b) = a × b
·1.3 欧几里得算法（辗转相除法）——必考！
原理： gcd(a, b) = gcd(b, a % b)，直到余数为0。
递归实现：
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
（2025年6月判断第1题：a大于b还是小于b都适用，正确）
迭代实现：
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
（2024年6月第5题）
练习题： gcd(48, 18) 的调用序列？
解析： gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0) → 返回6（2026年3月第4题）
练习题： gcd(105, 45) 的调用序列？
解析： gcd(105,45) → gcd(45,15) → gcd(15,0) → 返回15（2026年6月第4题）
欧几里得算法的时间复杂度： O(log n)（2025年6月第6题）
·1.4 唯一分解定理（算术基本定理）
定义： 任何一个大于1的自然数，都可以唯一地分解成有限个质数的乘积，不考虑顺序。（2024年3月第1题、2025年6月第8题）
例如： 30 = 2 × 3 × 5，20 = 2² × 5
易错判断题： “任何一个大于1的整数都可以唯一地分解为素数之和。”（2024年9月判断第3题）
·1.5 质因数分解
例题： 将正整数N分解为质因数乘积（2023年9月编程题1）
for (long long p = 2; p * p <= N; p++) {
if (N % p != 0) continue;
int cnt = 0;
while (N % p == 0) { cnt++; N /= p; }
// 输出 p 和 cnt（指数）
}
if (N > 1) { /* 处理剩余的质因子 */ }
·1.6 埃氏筛法（Eratosthenes筛法）
原理： 从2开始，每找到一个素数，就把它的所有倍数标记为合数。
vector<int> eratosthenes_sieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (int j = i * i; j <= n; j += i) // 从 i*i 开始，不是 2*i
is_prime[j] = false;
}
}
for (int i = sqrt(n) + 1; i <= n; i++)
if (is_prime[i]) primes.push_back(i);
return primes;
}
（2024年9月第5题：从j=i*i开始，不是j=i）
为什么从i²开始？ 因为小于i²的i的倍数（如2i, 3i, ...）已经被更小的质因子筛过了。（2026年3月第6题）
时间复杂度： O(n log log n)
·1.7 线性筛法（欧拉筛）——效率更高！
原理： 每个合数只被它的最小质因子筛掉一次，保证O(n)时间复杂度。
vector<int> linear_sieve(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) primes.push_back(i);
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) break; // 关键：保证每个合数只被最小质因子筛掉
}
}
return primes;
}
（2024年6月第7题、第8题：线性筛时间复杂度O(n)）
线性筛 vs 埃氏筛：
埃氏筛：一个合数可能被多个质数重复标记，如6会被2和3各标记一次
线性筛：每个合数只被其最小质因子筛掉一次（2024年12月判断第2题）
线性筛时间复杂度O(n)，低于埃氏筛的O(n log log n)（2024年9月判断第2题）
知识块②：算法复杂度
·2.1 时间复杂度
时间复杂度衡量算法运行时间随输入规模增长的速度。
常见复杂度从快到慢：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
O(1)： 常数时间，如数组随机访问 arr[i]
O(log n)： 对数时间，如二分查找
O(n)： 线性时间，如遍历数组
O(n log n)： 如归并排序、快速排序平均情况
O(n²)： 如冒泡排序、选择排序
O(2ⁿ)： 指数时间，如朴素递归斐波那契
·2.2 常见代码的时间复杂度分析
斐波那契数列——递归 vs 迭代：
朴素递归fiboB()：O(2ⁿ)（大量重复计算）（2024年3月第6题）
循环迭代 fiboA()：O(n)（2023年12月第1题）
判断素数——枚举到n vs 枚举到√n：
快速幂算法： O(log n)（2024年9月第8题）
·2.3 空间复杂度
空间复杂度衡量算法运行所需额外内存空间。
知识块③：链表——“动态的数据结构”
·3.1 什么是链表？
链表是由一系列结点组成的线性数据结构，每个结点包含数据域和指针域。结点之间通过指针连接，不需要连续的内存空间。（2024年6月判断第3题、2026年6月判断第1题）
数组 vs 链表：
（2024年9月第1题、2025年6月第1题）
·3.2 单链表
结构体定义：
struct Node {
int val;
Node* next;
};
在头部插入新节点（2026年6月第1题）：
newNode->next = head->next;
head->next = newNode;
删除指定节点（已知头结点，2025年12月第3题）：
// 单链表删除指定节点需要先找到前驱节点
SNode* prev = head;
while (prev->next != node) prev = prev->next;
prev->next = node->next;
delete node;
// 时间复杂度：O(n)
·3.3 双链表
结构体定义：
struct DNode {
int val;
DNode* prev;
DNode* next;
};
在头部插入（2024年6月第4题）：
p->prev = nullptr;
p->next = head;
if (head != nullptr) head->prev = p;
head = p;
删除中间节点（2026年6月第3题）：
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
// 时间复杂度：O(1) —— 已知节点指针情况下
（2025年12月第3题：双链表删除指定节点是O(1)，单链表是O(n)）
·3.4 循环链表
循环单链表遍历（2025年12月第1题）：
// 循环单链表的遍历——用 do-while
Node* p = head;
do {
cout << p->data << " ";
p = p->next;
} while (p != head); // 注意：不是 p != nullptr
循环链表判空（2026年3月第1题）：
在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身。
约瑟夫问题（循环链表经典应用，2025年6月第4题）：
用循环链表模拟n个人围成一圈，每次数到第k个人出圈。
知识块④：二分算法
·4.1 二分查找——“在有序数组中快速找目标”
原理： 每次取中间元素，与目标比较，缩小一半搜索范围。
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
（2025年3月第12题）
时间复杂度： O(log n)
前提条件： 数组必须是有序的（2024年3月判断第3题）
·4.2 二分查找的变体
查找第一个大于等于x的位置（lower_bound）：
int lowerBound(vector<int>& a, int x) {
int l = 0, r = a.size();
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
（2026年3月第8题、2026年6月第9题）
·4.3 二分答案（二分枚举法）
原理： 当问题的答案具有单调性时，可以对答案进行二分，用check函数验证。
经典例题：切木头（2025年12月第12题、2026年6月第10题）
bool check(int L, int K, int x) {
int cuts = (L - 1) / x;
return cuts <= K;
}
经典例题：在 [1,100] 内猜数，最多需要猜几次？→ 7次（log₂100 ≈ 7，2025年3月第11题）
知识块⑤：递归算法
·5.1 递归的概念
递归就是函数调用自身。一个递归函数必须包含终止条件，否则会无限递归导致栈溢出。
int factorial(int n) {
if (n <= 1) return 1; // 终止条件
return n * factorial(n - 1); // 递归调用
}
（2024年3月第3题、第14题）
·5.2 递归的优缺点
优点： 代码简洁，符合数学定义，易于理解（如斐波那契数列）
缺点：
递归调用占用栈空间，层数过多会导致栈溢出（2025年3月第7题）
递归通常比迭代更耗费内存空间（2024年12月判断第10题）
·5.3 递归 vs 迭代
斐波那契数列——递归实现（2023年12月第1题）：
int fiboA(int N) { // 递归，O(2ⁿ)
if (N == 1 || N == 2) return 1;
return fiboA(N - 1) + fiboA(N - 2);
}
斐波那契数列——循环实现：
int fiboB(int N) { // 循环，O(n)
if (N == 1 || N == 2) return 1;
int last2 = 1, last1 = 1, nowVal = 0;
for (int i = 2; i < N; i++) {
nowVal = last1 + last2;
last2 = last1;
last1 = nowVal;
}
return nowVal;
}
结论： 循环实现效率更高，递归实现更直观。（2023年12月第1题）
·5.4 递归的优化
尾递归优化： 如果递归调用是函数的最后一个操作，编译器可以优化，避免栈溢出。
记忆化递归： 用数组记录已经算过的结果，避免重复计算。
知识块⑥：分治算法
·6.1 分治的思想
分治： 将一个大问题分解成多个规模较小、结构相似的子问题，分别求解，再合并结果。（2024年6月第10题）
·6.2 归并排序
思想： 将数组分成两半，分别排序，再合并两个有序数组。（2024年6月第13题）
void mergeSort(int arr[], int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right); // 合并两个有序数组
}
合并操作： 双指针依次比较，将较小的放入结果数组（2026年3月第12题）
时间复杂度： 最好/最坏/平均都是 O(n log n)（2024年12月第10题）
空间复杂度： O(n)（需要额外数组存储合并结果）
稳定性： 稳定排序
merge函数被调用的次数： 对长度为n的数组，merge被调用 n-1 次（2026年6月第13题）
·6.3 快速排序
思想： 选择一个基准值（pivot），将数组分为小于pivot和大于pivot两部分，再递归排序。（2024年12月第9题）
void quickSort(vector<int>& arr, int low, int high) {
if (low >= high) return;
int pi = partition(arr, low, high); // 划分
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
时间复杂度：
最坏：O(n²)（数组已有序且每次选第一个元素为pivot，2024年9月第9题）
稳定性： 不稳定（2025年3月第9题）
如何避免最坏情况？ 随机选择pivot（2025年6月第14题），或三数取中法（2025年12月判断第6题）
·6.4 归并排序 vs 快速排序
知识块⑦：贪心算法
·7.1 贪心的核心思想
贪心算法： 在每一步选择中都选择当前状态下最优的选择（局部最优解），希望通过一系列局部最优选择达到全局最优。（2024年3月第2题）
注意： 贪心算法不一定能得到全局最优解！（2024年3月判断第4题、2024年9月判断第4题）
·7.2 最优子结构
最优子结构： 一个问题的最优解包含了其子问题的最优解。
「最优子结构」是贪心可以用到的前提，但满足最优子结构不意味着贪心一定能得到最优解。（2026年3月判断第8题）
·7.3 经典贪心问题
硬币找零（2024年6月第2题、2025年6月第13题）：
// 贪心：每次选当前最大面额的硬币
sort(coins.begin(), coins.end(), greater<int>());
for (int coin : coins) {
int num = amount / coin;
result[i] = num;
amount -= num * coin;
}
过河问题（2024年9月第11题）： 最轻的和最重的尝试一起过河
分饼干（2024年12月第13题）： 按利润从高到低排序，尽量安排
任务调度（2025年12月第14题）： 按利润从高到低，尽量安排
知识块⑧：C++高精度运算
·8.1 为什么需要高精度？
C++中的int（约±21亿）和long long（约±9×10¹⁸）能表示的整数范围有限。当需要处理上百位的超大整数时，需要用数组模拟。
·8.2 高精度加法
原理： 按位相加，处理进位。数组低位在前（个位在索引0）。
vector<int> add(vector<int> a, vector<int> b) {
vector<int> c;
int carry = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
c.push_back(carry % 10); // 存当前位
carry /= 10; // 进位
}
if (carry) c.push_back(carry); // 处理最高位进位
return c;
}
（2023年12月第11题、2025年12月第15题）
·8.3 高精度减法
原理： 按位相减，处理借位。保证被减数不小于减数。
vector<int> subtract(vector<int> a, vector<int> b) {
vector<int> c;
for (int i = 0; i < a.size(); i++) {
int digitB = (i < b.size()) ? b[i] : 0;
if (a[i] < digitB) {
a[i + 1]--; // 向高位借1
a[i] += 10; // 当前位加10
}
c.push_back(a[i] - digitB);
}
while (c.size() > 1 && c.back() == 0) c.pop_back(); // 去除前导0
return c;
}
（2024年6月第12题、2024年12月第15题、2026年6月第15题）
·8.4 高精度乘法
原理： 逐位相乘，累加进位。
vector<int> multiply(vector<int>& a, vector<int>& b) {
vector<int> c(a.size() + b.size(), 0);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
c[i + j] += a[i] * b[j];
int carry = 0;
for (int k = 0; k < c.size(); k++) {
int temp = c[k] + carry; // 当前位 + 进位
c[k] = temp % 10;
carry = temp / 10;
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
（2025年3月第15题）
·8.5 高精度除法（大数除以小数）
原理： 从高位到低位，逐位试商。
// 大整数（字符串表示）除以小整数（int）
vector<int> c;
long long rem = 0;
for (int i = 0; i < a.size(); i++) {
rem = rem * 10 + a[i];
int q = rem / b;
c.push_back(q);
rem %= b; // 余数
}
（2026年3月第15题）
