GESP C++ 五级真题详细分析讲解

GESP C++ 五级是一个明显的“分水岭”级别。

如果说三级、四级主要考 基础语法、数组、字符串、二维数组、排序，那么五级开始正式进入 算法学习阶段。五级题目不再只是把语法写对，而是要求你能根据题意选择合适的算法工具。

GESP C++ 五级的核心知识点主要包括：

1. 1. 数论核心
• ◦ 最大公约数 gcd
• ◦ 最小公倍数 lcm
• ◦ 质因数分解
• ◦ 筛法
• ◦ 唯一分解定理
2. 2. 快速幂
3. 3. 二分查找 / 二分答案
4. 4. 前缀和与差分
5. 5. 复杂贪心
6. 6. 位运算进阶
• ◦ 奇偶压缩
• ◦ 状态压缩入门
7. 7. 哈希表应用
• ◦ map
• ◦ unordered_map
• ◦ 计数与查找

一、GESP C++ 五级知识定位

1. 五级相比四级的变化

四级题通常是：

题目让你做什么，你就照着模拟。

五级题常常是：

题目表面看起来可以暴力做，但数据范围不允许，需要转换成数论、二分、前缀和或贪心模型。

2. 五级真题整体特点

GESP 五级真题通常有以下特征：

• • 数据范围变大，暴力容易超时
• • 数论题比例明显增加
• • 二分答案成为常见工具
• • 前缀和、差分用于优化区间统计或区间修改
• • 贪心题需要理解“为什么这样选最优”
• • 会出现 long long
• • 更强调时间复杂度分析

二、五级真题常见模块总览

三、模块一：GCD 与 LCM

1. 最大公约数 GCD

题型描述

给定两个整数 a 和 b，求它们的最大公约数。

例如：

a = 12, b = 18gcd = 6

2. 辗转相除法

核心公式：

gcd(a, b) = gcd(b, a % b)

直到 b == 0。

代码模板

intgcd(int a, int b){while (b != 0) {int r = a % b;        a = b;        b = r;    }return a;}

也可以直接使用 C++ 内置函数：

#include<numeric>__gcd(a, b);

在竞赛中很多同学会写：

#include<bits/stdc++.h>usingnamespace std;int g = __gcd(a, b);

3. 最小公倍数 LCM

公式：

lcm(a, b) = a / gcd(a, b) * b

注意推荐写成：

a / gcd(a, b) * b

而不是：

a * b / gcd(a, b)

因为 a * b 可能先溢出。

代码模板

longlonglcm(longlong a, longlong b){return a / __gcd(a, b) * b;}

4. 常见真题考法

考法一：分数约分

输入分子 a 和分母 b，输出最简分数。

思路：

g = gcd(a, b)a /= gb /= g

示例代码

#include<bits/stdc++.h>usingnamespace std;intmain(){longlong a, b;    cin >> a >> b;longlong g = __gcd(a, b);    cout << a / g << "/" << b / g << endl;return0;}

考法二：判断两个数是否互质

两个数互质当且仅当：

gcd(a, b) == 1

考法三：多个数的 GCD

longlong ans = a[1];for (int i = 2; i <= n; i++) {    ans = __gcd(ans, a[i]);}

5. 易错点

四、模块二：质数、质因数分解与筛法

五级数论题比例很高，质数相关是重点。

1. 判断质数

虽然素数判断在低级别已经出现，但五级会把它和更复杂问题结合。

代码模板

boolisPrime(int x){if (x < 2) returnfalse;for (int i = 2; i * i <= x; i++) {if (x % i == 0) returnfalse;    }returntrue;}

注意

1 不是质数。

2. 质因数分解

题型描述

把一个整数分解成若干质数的乘积。

例如：

60 = 2^2 × 3 × 5

3. 质因数分解模板

voidfactorize(longlong n){for (longlong i = 2; i * i <= n; i++) {if (n % i == 0) {int cnt = 0;while (n % i == 0) {                n /= i;                cnt++;            }            cout << i << " " << cnt << endl;        }    }if (n > 1) {        cout << n << " " << 1 << endl;    }}

4. 为什么循环到 sqrt(n) 就够？

如果 n 有一个大于 sqrt(n) 的因子，那么它一定对应一个小于 sqrt(n) 的因子。

所以只需要枚举到：

i * i <= n

注意不要写成：

i <= sqrt(n)

因为 sqrt 是浮点函数，可能有精度问题。

5. 唯一分解定理

任何大于 1 的整数都可以唯一分解为：

n = p1^a1 × p2^a2 × ... × pk^ak

其中 p1, p2, ... 是不同质数。

五级中常见的题目会利用它来做：

• • 因数个数
• • 因数和
• • 判断平方数
• • 判断两个数的质因子结构
• • 化简数字条件

6. 因数个数公式

如果：

n = p1^a1 × p2^a2 × ... × pk^ak

那么 n 的正因数个数为：

(a1 + 1)(a2 + 1)...(ak + 1)

例子

60 = 2^2 × 3^1 × 5^1因数个数 = (2+1)(1+1)(1+1) = 12

7. 筛法求质数

如果需要判断很多个数是否为质数，反复试除会慢，可以用筛法。

埃氏筛模板

constint N = 1000000;bool isPrime[N + 5];voidsieve(){for (int i = 0; i <= N; i++) {        isPrime[i] = true;    }    isPrime[0] = isPrime[1] = false;for (int i = 2; i * i <= N; i++) {if (isPrime[i]) {for (int j = i * i; j <= N; j += i) {                isPrime[j] = false;            }        }    }}

8. 质数模块易错点

五、模块三：快速幂

快速幂是五级常见算法，用来快速计算：

a^b mod p

如果直接循环乘 b 次，当 b 很大时会超时。

1. 快速幂思想

利用二进制拆分指数。

例如：

13 = 8 + 4 + 1a^13 = a^8 × a^4 × a^1

每次让底数平方，指数右移。

2. 快速幂模板

longlongqpow(longlong a, longlong b, longlong mod){longlong ans = 1 % mod;while (b > 0) {if (b & 1) {            ans = ans * a % mod;        }        a = a * a % mod;        b >>= 1;    }return ans;}

3. 真题常见考法

考法一：直接求幂取模

输入 a, b, p，求 a^b mod p

考法二：公式中包含指数

例如：

求 2^n - 1 mod p

写法：

(qpow(2, n, p) - 1 + p) % p

注意减法取模时要加 p，避免负数。

4. 快速幂易错点

六、模块四：二分查找与二分答案

五级的另一个核心是二分。

二分分两类：

1. 1. 二分查找
• ◦ 在有序数组中找某个值
2. 2. 二分答案
• ◦ 答案满足单调性，通过 check 判断

1. 二分查找

1.1 基础模板

在升序数组中查找 x 是否存在：

int l = 1, r = n;bool found = false;while (l <= r) {int mid = (l + r) / 2;if (a[mid] == x) {        found = true;break;    } elseif (a[mid] < x) {        l = mid + 1;    } else {        r = mid - 1;    }}

1.2 查找第一个大于等于 x 的位置

int l = 1, r = n, ans = n + 1;while (l <= r) {int mid = (l + r) / 2;if (a[mid] >= x) {        ans = mid;        r = mid - 1;    } else {        l = mid + 1;    }}

也可以使用 STL：

lower_bound(a + 1, a + n + 1, x);

2. 二分答案

二分答案是五级最重要的思维之一。

2.1 什么题适合二分答案？

通常题目会问：

• • 最大值最小
• • 最小值最大
• • 最少需要多少
• • 最多能做到多少
• • 能否在某个限制内完成

并且具有单调性。

2.2 单调性是什么？

例如：

如果距离为 10 可以做到，那么距离为 9 通常也可以做到。

或者：

如果花费 100 可以完成，那么花费 120 也一定可以完成。

这种“可以 / 不可以”随着答案变化呈现一边可行、一边不可行的性质，就可以二分。

2.3 二分答案基本模板：求最小可行值

int l = 0, r = 1000000000;int ans = r;while (l <= r) {int mid = l + (r - l) / 2;if (check(mid)) {        ans = mid;        r = mid - 1;    } else {        l = mid + 1;    }}cout << ans << endl;

含义：

• • check(mid) == true：说明 mid 可行，可以尝试更小
• • check(mid) == false：说明 mid 太小，需要变大

2.4 二分答案基本模板：求最大可行值

int l = 0, r = 1000000000;int ans = l;while (l <= r) {int mid = l + (r - l) / 2;if (check(mid)) {        ans = mid;        l = mid + 1;    } else {        r = mid - 1;    }}cout << ans << endl;

含义：

• • check(mid) == true：说明 mid 可行，可以尝试更大
• • check(mid) == false：说明 mid 太大，需要变小

2.5 二分答案常见真题模型

模型一：最大化最小值

例如：

给定若干位置，选出若干个点，使相邻点之间的最小距离尽量大。

做法：

1. 1. 二分答案 d
2. 2. check(d) 判断能不能做到最小距离至少为 d
3. 3. 如果能做到，尝试更大的 d

模型二：最小化最大值

例如：

把任务分成若干组，使每组总量的最大值尽量小。

做法：

1. 1. 二分最大值 x
2. 2. check(x) 判断能不能在限制内分组
3. 3. 如果能做到，尝试更小的 x

2.6 二分易错点

七、模块五：前缀和

前缀和用于快速求区间和。

1. 一维前缀和

给定数组：

a[1], a[2], ..., a[n]

定义：

s[i] = a[1] + a[2] + ... + a[i]

那么区间 [l, r] 的和为：

s[r] - s[l - 1]

2. 一维前缀和模板

longlong a[100005], s[100005];for (int i = 1; i <= n; i++) {    cin >> a[i];    s[i] = s[i - 1] + a[i];}

查询：

longlong ans = s[r] - s[l - 1];

3. 常见真题考法

考法一：多次区间求和

如果有很多次询问：

每次问 a[l] + ... + a[r]

暴力每次循环会慢，前缀和可以做到每次 O(1)。

考法二：枚举区间优化

有时需要枚举所有区间 [l, r] 的和。

暴力求和是三层：

for lfor rfor k=l..r

用前缀和后变成：

for (int l = 1; l <= n; l++) {for (int r = l; r <= n; r++) {longlong sum = s[r] - s[l - 1];    }}

减少一层循环。

4. 二维前缀和是否属于五级？

GESP 五级主要是前缀和与差分，实际题目中以一维为主。如果出现简单二维表格求区域和，方法类似，但一般不会作为五级核心难点。

5. 前缀和易错点

八、模块六：差分

差分适合处理：

多次区间修改，最后求每个位置的值。

1. 差分思想

如果原数组是 a，差分数组 d 定义为：

d[i] = a[i] - a[i - 1]

那么可以通过前缀和还原：

a[i] = d[1] + d[2] + ... + d[i]

2. 区间加法

如果要把 [l, r] 每个数都加上 x，只需要：

d[l] += x;d[r + 1] -= x;

最后做一次前缀和还原。

3. 差分模板

longlong d[100005];int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {longlong x;    cin >> x;    d[i] += x;    d[i + 1] -= x;}for (int i = 1; i <= m; i++) {int l, r;longlong x;    cin >> l >> r >> x;    d[l] += x;    d[r + 1] -= x;}longlong cur = 0;for (int i = 1; i <= n; i++) {    cur += d[i];    cout << cur << " ";}

4. 更常见写法

先读原数组 a，再建差分：

for (int i = 1; i <= n; i++) {    cin >> a[i];}for (int i = 1; i <= n; i++) {    d[i] = a[i] - a[i - 1];}

区间修改：

d[l] += x;d[r + 1] -= x;

还原：

for (int i = 1; i <= n; i++) {    a[i] = a[i - 1] + d[i];}

5. 差分易错点

九、模块七：复杂贪心

五级的贪心比三级、四级更难一些，不只是简单排序。

1. 贪心题的核心

贪心就是：

每一步都做当前看起来最优的选择，并且这个选择能够导向全局最优。

但难点在于：

• • 怎么定义“当前最优”
• • 为什么这样做一定对
• • 有没有反例

2. 常见贪心模型

模型一：排序后选择

例如：

有若干物品，每个物品有价值或代价，要求尽量多选或尽量少花费。

常见做法：

• • 按代价从小到大排序
• • 按结束时间从小到大排序
• • 按收益从大到小排序
• • 按某个比例排序

模型二：区间贪心

例如：

选择尽可能多的不重叠区间。

经典策略：

按右端点从小到大排序，每次选择能选的最早结束区间。

模型三：反悔贪心入门

五级有时会出现“先选，后面如果发现更优就替换”的思想。

常用工具是：

priority_queue

不过五级通常不会考得特别深。

3. 贪心解题步骤

1. 1. 找目标：最大化什么？最小化什么？
2. 2. 找限制：每次能选什么？
3. 3. 想排序规则
4. 4. 尝试构造反例
5. 5. 写代码
6. 6. 用样例和极端数据验证

4. 贪心易错点

十、模块八：哈希表应用

五级开始会出现更灵活的统计与查找。

如果数值范围很大，不能开普通计数数组，就可以用：

mapunordered_map

1. map

map 会自动按键排序。

map<int, int> cnt;cnt[x]++;

遍历：

for (auto p : cnt) {    cout << p.first << " " << p.second << endl;}

2. unordered_map

unordered_map 平均查找更快，但不保证顺序。

unordered_map<int, int> cnt;cnt[x]++;

3. 常见真题考法

考法一：统计出现次数

map<int, int> cnt;for (int i = 1; i <= n; i++) {int x;    cin >> x;    cnt[x]++;}

考法二：判断是否出现过

unordered_map<int, bool> vis;vis[x] = true;if (vis[y]) {// y 出现过}

考法三：两数之和类问题

判断是否存在两个数之和为 k。

unordered_map<int, int> cnt;for (int i = 1; i <= n; i++) {int x;    cin >> x;if (cnt[k - x] > 0) {        cout << "Yes" << endl;return0;    }    cnt[x]++;}cout << "No" << endl;

4. 哈希表易错点

十一、五级真题综合题型分析

GESP 五级真题经常不是单一知识点，而是组合题。

1. 数论 + 枚举

题型特征

题目给出一个范围，要求统计满足某种数论性质的数。

常见性质：

• • 是否为质数
• • 是否互质
• • 因数个数
• • 质因子个数
• • 是否能被某些数整除

解题套路

1. 1. 判断是否需要预处理
2. 2. 数据小：直接枚举 + 判断
3. 3. 数据大：筛法 / 预处理
4. 4. 注意 long long

2. 二分 + 贪心

这是五级中比较有代表性的组合。

题型特征

题目要求：

最大化最小值最小化最大值最多能完成多少最少需要多少

通常需要：

1. 1. 二分答案
2. 2. 用贪心写 check

常见结构

boolcheck(int x){// 贪心判断 x 是否可行}

主程序：

while (l <= r) {int mid = (l + r) / 2;if (check(mid)) {        ans = mid;        l = mid + 1; // 或 r = mid - 1    } else {        r = mid - 1; // 或 l = mid + 1    }}

关键是判断你要求的是最大可行还是最小可行。

3. 前缀和 + 枚举

题型特征

题目要求大量区间和，如果每次重新累加会超时。

常见结构

for (int l = 1; l <= n; l++) {for (int r = l; r <= n; r++) {longlong sum = s[r] - s[l - 1];// 判断 sum 是否满足条件    }}

4. 差分 + 区间修改

题型特征

题目有很多次操作：

把 l 到 r 都加上 x最后输出所有位置

或者：

经过若干区间影响后，问每个位置最终值

解题套路

1. 1. 建差分数组
2. 2. 每个操作 d[l]+=x, d[r+1]-=x
3. 3. 最后前缀还原

十二、五级真题难度分布

一套 GESP C++ 五级题通常可以这样理解：

当然不同批次真题会有变化，但五级主线非常明确：

数论 + 二分 + 前缀和差分 + 贪心。

十三、五级考试解题流程建议

第一步：看数据范围

五级题一定要看数据范围。

如果：

n <= 1000

可能可以双重循环。

如果：

n <= 100000

通常需要：

• • 排序
• • 前缀和
• • 差分
• • 二分
• • 哈希表

如果：

数值 <= 10^6

可能考虑筛法或计数数组。

第二步：判断题型关键词

第三步：先写核心函数

五级题建议先写核心函数，比如：

• • gcd
• • isPrime
• • qpow
• • check
• • cmp

尤其是二分答案题，一定先写清楚：

boolcheck(longlong x)

表示什么。

第四步：检查复杂度

写完思路后问自己：

最多会循环多少次？会不会是 O(n^2)？n=100000 时能不能过？

常见复杂度参考：

十四、五级必背代码模板汇总

1. GCD

longlonggcd(longlong a, longlong b){while (b) {longlong r = a % b;        a = b;        b = r;    }return a;}

2. LCM

longlonglcm(longlong a, longlong b){return a / gcd(a, b) * b;}

3. 判断质数

boolisPrime(longlong x){if (x < 2) returnfalse;for (longlong i = 2; i * i <= x; i++) {if (x % i == 0) returnfalse;    }returntrue;}

4. 质因数分解

for (longlong i = 2; i * i <= n; i++) {if (n % i == 0) {int cnt = 0;while (n % i == 0) {            n /= i;            cnt++;        }// i 是质因子，cnt 是指数    }}if (n > 1) {// n 是剩余的大质因子，指数为 1}

5. 埃氏筛

constint N = 1000000;bool prime[N + 5];voidsieve(){for (int i = 0; i <= N; i++) prime[i] = true;    prime[0] = prime[1] = false;for (int i = 2; i * i <= N; i++) {if (prime[i]) {for (int j = i * i; j <= N; j += i) {                prime[j] = false;            }        }    }}

6. 快速幂

longlongqpow(longlong a, longlong b, longlong mod){longlong ans = 1 % mod;while (b) {if (b & 1) ans = ans * a % mod;        a = a * a % mod;        b >>= 1;    }return ans;}

7. 前缀和

for (int i = 1; i <= n; i++) {    cin >> a[i];    s[i] = s[i - 1] + a[i];}longlong sum = s[r] - s[l - 1];

8. 差分

for (int i = 1; i <= n; i++) {    cin >> a[i];    d[i] = a[i] - a[i - 1];}d[l] += x;d[r + 1] -= x;for (int i = 1; i <= n; i++) {    a[i] = a[i - 1] + d[i];}

9. 二分答案：最大可行值

longlong l = 0, r = 1e18, ans = 0;while (l <= r) {longlong mid = l + (r - l) / 2;if (check(mid)) {        ans = mid;        l = mid + 1;    } else {        r = mid - 1;    }}

10. 二分答案：最小可行值

longlong l = 0, r = 1e18, ans = r;while (l <= r) {longlong mid = l + (r - l) / 2;if (check(mid)) {        ans = mid;        r = mid - 1;    } else {        l = mid + 1;    }}

十五、五级常见失分点总表

十六、五级备考重点

第一阶段：数论基础

必须掌握：

• • gcd
• • lcm
• • 判断质数
• • 质因数分解
• • 因数个数
• • 筛法

这一部分是五级的高频核心。

第二阶段：快速幂与取模

重点掌握：

• • 快速幂模板
• • 每步取模
• • 减法取模
• • long long
• • 不要把 ^ 当乘方

第三阶段：前缀和与差分

重点练：

• • 一维前缀和
• • 多次区间查询
• • 差分区间修改
• • 前缀还原
• • 下标边界

第四阶段：二分答案

这是五级最容易拉开差距的部分。

重点练：

• • 判断单调性
• • 写 check
• • 区分最大可行 / 最小可行
• • 正确设置 l 和 r

第五阶段：贪心与综合题

重点练：

• • 排序贪心
• • 区间贪心
• • 二分 + 贪心
• • 前缀和 + 枚举
• • 数论 + 枚举

十七、从五级到六级的衔接

GESP 五级通过后，六级会进入 动态规划和图搜索 的阶段，主要包括：

• • 线性 DP
• • 背包 DP
• • 简单树形 DP
• • DFS / BFS
• • 栈的应用
• • 归并排序与逆序对
• • 图的遍历

所以五级和六级之间又是一次明显升级：

如果五级能稳定 90 分以上，可以开始学习六级。

如果五级只有 60~80 分，建议先不要急着冲六级，应重点补：

• • GCD / LCM
• • 质因数分解
• • 二分答案
• • 前缀和 / 差分
• • 快速幂

十八、五级考前检查清单

考前可以逐项确认：

数论

• • 我会不会手写 gcd？
• • 我是否知道 lcm = a / gcd(a,b) * b？
• • 我能不能判断质数？
• • 我能不能做质因数分解？
• • 我是否知道 1 不是质数？
• • 我是否会用筛法预处理质数？

快速幂

• • 我会不会写快速幂模板？
• • 我是否知道 C++ 中 ^ 不是乘方？
• • 我是否每一步都取模？
• • 我是否会处理 (x-y+mod)%mod？

二分

• • 我能不能判断一道题是否有单调性？
• • 我会不会写 check 函数？
• • 我是否能区分最大可行和最小可行？
• • 我是否会设置正确的左右边界？

前缀和 / 差分

• • 我是否会写 s[i]=s[i-1]+a[i]？
• • 我是否记得区间和是 s[r]-s[l-1]？
• • 我是否会用差分做区间加？
• • 我是否记得 d[r+1]-=x？
• • 我是否知道最后要前缀还原？

贪心 / 哈希

• • 我是否会写排序比较函数？
• • 我是否能解释自己的贪心策略？
• • 我是否会用 map 统计次数？
• • 我是否知道 map 和 unordered_map 的区别？

十九、总结

GESP C++ 五级的核心可以概括为：

用数论解决整数问题，用前缀和 / 差分优化区间问题，用二分答案处理单调性问题，用贪心处理局部选择问题。

五级最重要的四大能力是：

1. 1. 数论能力
• ◦ gcd
• ◦ lcm
• ◦ 质因数分解
• ◦ 筛法
2. 2. 复杂度优化能力
• ◦ 从暴力循环转向 O(log n)、O(n)、O(n log n)
3. 3. 二分建模能力
• ◦ 找答案范围
• ◦ 找单调性
• ◦ 写 check
4. 4. 区间处理能力
• ◦ 前缀和查区间
• ◦ 差分改区间

如果这些内容掌握扎实，GESP C++ 五级就可以稳定通过，并为六级的 DP、搜索和图论打下基础。