GESP C++ 五级编程真题必备程序（必背模板）

本章是五级备考的"速通手册"。我们统计了 2023 年 9 月至 2026 年 6 月 共 12 场真实认证（来源：CCF GESP 官方真题、洛谷题单、各机构真题解析）的编程题，归纳出出现频率最高的 6 大类核心程序。把它们背熟、写熟，编程题就稳了。

说明：下列模板均按 C++17（GESP 考试环境 g++） 书写，可直接复制到考场再按题意微调。每个模板下方都附了"真题出处"，方便你对照练习。

五级编程真题核心模板速查

49.1 数论三件套（出现频率最高，必背）

数论是五级编程题的"重灾区"，几乎每场都有：最大公因数(2025.06)、因数分解(2023.09)、B-smooth 数(2024.03)、原根判断(2025.03)、奇妙数字(2024.12) 都属此类。只要掌握下面三个模板，这类题基本都能拿下。

49.1.1 最大公约数 GCD 与最小公倍数 LCM

原理： $\gcd(a,b)=\gcd(b, a\bmod b)$ ，递归到 $b=0$ 时 $a$ 即为答案； $\operatorname{lcm}(a,b)=\dfrac{a\times b}{\gcd(a,b)}$ ，先除后乘防止 long long 溢出。

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);   // 辗转相除法
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;            // 先除后乘，避免 a*b 溢出
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << gcd(a, b) << " " << lcm(a, b) << "\n";
    return 0;
}

真题贴士：2025.06「最大公因数」要求对 $n$ 个数整体求 $\gcd$ 。利用 $\gcd(a_1,a_2,\dots,a_k)=\gcd(\gcd(a_1,\dots,a_{k-1}),a_k)$ ，把上面 gcd 在循环里依次叠加即可。

49.1.2 素数筛：埃氏筛与线性筛

埃氏筛：标记每个素数的倍数为合数，内层从 $i\times i$ 起（更小的倍数已被更小素数筛过），复杂度 $O(n\log\log n)$ 。
线性筛（欧拉筛）：每个合数只被"最小质因子"筛一次，复杂度 $O(n)$ ，五级客观题常考其 if (i % prime[j] == 0) break; 这句。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000005;
bool isPrime[N];          // 埃氏筛：true 表示素数
int  prime[N], cnt;       // 线性筛：素数列表
bool isComp[N];           // 线性筛：true 表示合数

// 埃氏筛：筛出 [2, n] 内所有素数
void sieve(int n) {
    memset(isPrime, 1, sizeof(isPrime));
    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;
}

// 线性筛：每个合数只被最小质因子筛一次
void linearSieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isComp[i]) prime[cnt++] = i;
        for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
            isComp[i * prime[j]] = true;
            if (i % prime[j] == 0) break;   // 关键：保证最小质因子
        }
    }
}

int main() {
    int n; cin >> n;
    sieve(n);
    for (int i = 2; i <= n; i++)
        if (isPrime[i]) cout << i << " ";
    return 0;
}

49.1.3 质因数分解

原理：从 $2$ 试除到 $\sqrt{n}$ ，能整除就不断除尽；最后若剩余 $n>1$ ，它本身就是质因子（唯一分解定理）。

#include <iostream>
using namespace std;

// 输出 n 的所有质因子（可重复）
void factorize(int n) {
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
    if (n > 1) cout << n;   // 剩下的部分是大于 sqrt 的质因子
}

int main() {
    int n; cin >> n;
    factorize(n);
    return 0;
}

真题贴士：2023.09「因数分解」、2024.03「B-smooth 数」（判断所有质因子是否都不超过某个界 $B$ ）都用这个框架，只需在循环里加一句"若 $i>B$ 则不满足"。

49.2 高精度运算（大整数，编程大题高频）

当数字超出 long long 范围（如 2026.03「有限不循环小数」），用数组逆序存储模拟竖式。约定：个位存下标 0，高位在下标大的位置，方便进位向前传递。字符串读入后 reverse 再逐字符转数字。

49.2.1 高精度加法

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> add(const vector<int>& a, const vector<int>& b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < a.size() || i < b.size() || carry; i++) {
        int x = i < a.size() ? a[i] : 0;
        int y = i < b.size() ? b[i] : 0;
        c.push_back((x + y + carry) % 10);
        carry = (x + y + carry) / 10;
    }
    return c;
}

int main() {
    string s, t; cin >> s >> t;
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    vector<int> a, b;
    for (char c : s) a.push_back(c - '0');
    for (char c : t) b.push_back(c - '0');
    vector<int> c = add(a, b);
    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    return 0;
}

49.2.2 高精度乘法

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> mul(const vector<int>& a, const 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 i = 0; i < c.size(); i++) {     // 统一进位
        c[i] += carry;
        carry = c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();  // 去前导 0
    return c;
}

要点：减法需先比较大小、借位；除法（大整数 ÷ 小整数）用"上一位余数 ×10 + 当前位"再 % 取余。客观题里高精度四则都考过，编程大题多为加/乘。

49.3 链表操作（客观题必考，编程保底）

近几年五级编程题较少出现链表大题，但选择/判断题必考（单/双/循环链表的插入、删除、遍历、反转）。下面给出最通用的单链表框架，务必能手写。

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}   // 构造函数
};

// 尾插法建立单链表
Node* build(int arr[], int n) {
    Node *head = nullptr, *tail = nullptr;
    for (int i = 0; i < n; i++) {
        Node* p = new Node(arr[i]);
        if (!head) head = tail = p;
        else { tail->next = p; tail = p; }
    }
    return head;
}

// 遍历输出
void print(Node* head) {
    for (Node* p = head; p; p = p->next) cout << p->val << " ";
}

// 单链表反转（真题常考）
Node* reverseList(Node* head) {
    Node *prev = nullptr, *cur = head;
    while (cur) {
        Node* nxt = cur->next;   // 先存后继
        cur->next = prev;        // 指针反向
        prev = cur; cur = nxt;
    }
    return prev;
}

// 删除值为 x 的结点（用哑结点统一头删与中间删）
Node* removeVal(Node* head, int x) {
    Node dummy(0); dummy.next = head;
    Node* cur = &dummy;
    while (cur->next) {
        if (cur->next->val == x) cur->next = cur->next->next;
        else cur = cur->next;
    }
    return dummy.next;
}

int main() {
    int a[] = {1, 2, 3};
    Node* h = build(a, 3);
    print(reverseList(h));   // 输出 3 2 1
    return 0;
}

易错：循环链表没有 nullptr 终止条件，遍历一圈的停止条件是 p->next == head；删除结点必须先找到前驱。

49.4 二分（查找 + 答案，编程题第二大高频）

二分是五级编程题第二大高频考点：找数(2026.03)、奖品兑换(2025.06，二分答案)、数字移动(2025.12)、烦恼的高考志愿(洛谷，二分查找)。

49.4.1 二分查找（求下界 lower_bound）

在升序数组中找"第一个 $\ge x$ "的位置，模板如下（l < r 配合 r = mid 不会死循环）：

#include <iostream>
#include <vector>
using namespace std;

// 返回第一个 >= x 的下标；都不满足则返回 a.size()
int lower_bound(const vector<int>& a, int x) {
    int l = 0, r = a.size(), mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (a[mid] >= x) r = mid;   // 可能答案，收缩右界
        else l = mid + 1;
    }
    return l;
}

49.4.2 二分答案（求"最大/最小满足条件的值"）

当答案具有单调性时，把"求最优值"转化为"判断某个值是否可行"。典型如：给定 $n$ 根木头切出不少于 $m$ 段等长木段，求最大长度。

#include <iostream>
#include <vector>
using namespace std;

// check(mid)：长度为 mid 时能否切出 >= m 段（示例逻辑）
bool check(const vector<int>& a, int m, int mid) {
    long long cnt = 0;
    for (int x : a) cnt += x / mid;
    return cnt >= m;
}

// 求最大可行长度
int binaryAnswer(const vector<int>& a, int m) {
    int l = 1, r = 1000000000, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(a, m, mid)) { ans = mid; l = mid + 1; }  // 可行，试着更大
        else r = mid - 1;
    }
    return ans;
}

口诀：check 为真时，若求最大就 l = mid + 1 并记下 ans；若求最小就 r = mid - 1 并记下 ans。写反就会 WA。

49.5 分治与排序（快排 / 归并 / 结构体排序）

分治思想贯穿五级。成绩排序(2024.03) 考结构体自定义排序；归并、快排既考客观（复杂度、稳定性）也常作编程底座。

49.5.1 快速排序（平均 $O(n\log n)$ ，最坏 $O(n^2)$ ）

#include <iostream>
using namespace std;

void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[(l + r) / 2];   // 取中间作基准
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) { swap(a[i], a[j]); i++; j--; }
    }
    quickSort(a, l, j);
    quickSort(a, i, r);
}

49.5.2 归并排序（稳定， $O(n\log n)$ ）

#include <iostream>
using namespace std;

int tmp[100005];
void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= 保证稳定
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];
}

49.5.3 结构体排序（成绩排序真题）

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

struct Stu { string name; int score; };
bool cmp(const Stu& a, const Stu& b) {
    if (a.score != b.score) return a.score > b.score;  // 分数降序
    return a.name < b.name;                            // 同分按名字字典序
}
// 调用：sort(stu, stu + n, cmp);

49.6 贪心策略（区间调度 / 活动选择）

贪心要求"局部最优能推出全局最优"。武器强化(2024.12)、活动选择类题都属此类。最经典的是区间调度：选最多互不重叠的活动，策略是"按结束时间升序，能选就选"。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Seg { int l, r; };
bool cmp(const Seg& a, const Seg& b) { return a.r < b.r; }   // 按结束时间贪心

int activitySelect(vector<Seg>& s) {
    sort(s.begin(), s.end(), cmp);
    int cnt = 0, last = -1;
    for (auto& seg : s)
        if (seg.l >= last) { cnt++; last = seg.r; }   // 不冲突就选
    return cnt;
}

注意：01 背包等问题不能贪心（要 DP）。先判断是否满足"最优子结构 + 贪心选择性"，再动手。

49.7 考场速记 · 高频易错点

数论：lcm 先除后乘防溢出；筛法从 i=2 起，1 不是素数；埃氏筛内层从 i*i 起。
高精度：逆序存储（个位下标 0）；进位循环别漏最后剩余进位；减法先比大小。
链表：循环链表终止条件是 p->next == head，不是 nullptr；删结点必存前驱。
二分：查找只对有序数组；二分答案必须有 check，ans 更新方向别写反。
分治：快排最坏 $O(n^2)$ （已排序数组 + 取首元素为基准），归并稳定 $O(n\log n)$ ；递归终止条件 l >= r 必写。
贪心：01 背包不能贪心，用 DP。
溢出：大数相乘、lcm 一律用 long long，int 仅到 $2\times10^9$ 。

49.8 自测练习（参考答案折叠）

关于 $\operatorname{lcm}(a,b)$ 的写法，下列哪一种最安全（不易溢出）？ A. a * b / gcd(a, b) B. a / gcd(a, b) * b C. gcd(a, b) * a * b D. b / gcd(a, b) * a * b

查看答案
答案：B。先除以 $\gcd$ 再乘，能把中间结果降到最小，避免 a*b 在 long long 范围内就溢出。注意 long long 也仅约 $9\times10^{18}$ ，极端数据仍需高精度。
埃氏筛中将内层循环从 j = 2*i 改为 j = i*i 的主要原因是？ A. 2*i 一定不是合数 B. 小于 i*i 的 i 的倍数已被更小素数筛过 C. 可以把复杂度降为 $O(n)$ D. i*i 一定是素数

查看答案
答案：B。当 i 是素数时，其小于 i*i 的倍数（如 $2i,3i,\dots$ ）必然已被更小的素数因子筛除，直接从 i*i 起可减少重复标记。复杂度仍是 $O(n\log\log n)$ ，不是 $O(n)$ （那是线性筛）。
在升序数组中用二分求"第一个 $\ge x$ "的位置，当 a[mid] >= x 时应执行？ A. r = mid - 1 B. l = mid + 1 C. r = mid D. l = mid

查看答案
答案：C。当前 mid 可能是答案或答案在左侧，为不漏掉把右界收到 mid（r = mid），配合 l < r 的循环条件不会死循环。若写 r = mid - 1 可能跳过真正的下界。
线性筛中 if (i % prime[j] == 0) break; 的作用是？ A. 提前结束外层循环 B. 保证每个合数只被其最小质因子筛一次 C. 跳过偶数 D. 防止数组越界

查看答案
答案：B。当 i 能被当前素数 prime[j] 整除时，i*prime[j+1] 的最小质因子其实是 prime[j] 而非 prime[j+1]，若继续会让该合数被更大的素数重复筛；break 确保每个合数仅由最小质因子筛除，从而保证 $O(n)$ 与正确性。
下列哪类问题不能用贪心算法保证得到全局最优解？ A. 活动选择（选最多不重叠区间） B. 区间调度 C. 0-1 背包（物品不可分割） D. 按结束时间贪心的资源分配

查看答案
答案：C。0-1 背包中物品不可分割，局部最优（先放性价比高的）不能保证全局最优，必须用动态规划。A、B、D 都满足贪心选择性，可用贪心。