【GESP】C++五级真题 luogu-P17011 [GESP202606 五级] 晚宴
GESP C++五级2026年6月真题。本题考查最大公约数（GCD）与枚举，需要在所有互质的菜肴对中找出美味度之和的最大值。难度⭐⭐。本题在洛谷评定为普及-。
luogu-P17011 [GESP202606 五级] 晚宴
题目要求
题目描述
小明去参加晚宴。晚宴中有 $n$ 个菜肴，每个菜肴都有一个美味度，第 $i$ 个菜肴的美味度为 $v_i$。
晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 $1$）。
请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。
输入格式
输入 $2$ 行，
第一行为一个正整数 $n$，表示菜肴的个数；
第二行为 $n$ 个整数 $v_1, v_2, \cdots, v_n$ 表示菜肴的美味度，整数之间以空格分隔。
输出格式
输出一个整数，表示两道互质菜肴美味度之和的最大值。
输入输出样例 #1
输入 #1
1
2
5
3 5 7 35 105
输出 #1
1
38
说明/提示
最优选择是 $3$ 和 $35$。
注意到，$105$ 与其他任意菜肴的最大公约数都大于 $1$，因此无法参与合法选择。
数据范围
$2 \le n \le 1000$，$1 \le v_i \le 1000000$。
数据保证不存在相同美味度的菜肴。
数据保证至少存在一种选取两道菜肴的方案。
题目分析
本题的核心是从 $n$ 个菜肴中选取两道美味度互质（$\gcd = 1$）的菜肴，使得美味度之和最大。
1. 互质的判定
两个整数 $a$、$b$ 互质，当且仅当 $\gcd(a, b) = 1$。可以用 辗转相除法（欧几里得算法） 高效计算最大公约数：
\[\gcd(a, b) = \gcd(b, a \bmod b)\]当 $b = 0$ 时，$\gcd(a, 0) = a$。C++ 中可以使用 __gcd() 函数或自行实现。
2. 枚举策略
数据范围 $n \le 1000$，因此可以枚举所有的二元组 $(i, j)$，共 $\frac{n(n-1)}{2}$ 对，最多约 $500000$ 对。对每一对判断是否互质，若互质则更新答案。
具体步骤：
- 读入所有菜肴的美味度
- 双重循环枚举所有不同的菜肴对 $(i, j)$（其中 $i < j$）
- 对每一对计算 $\gcd(v_i, v_j)$，若结果为 $1$，则用 $v_i + v_j$ 更新最大值
- 输出最大值
3. 样例验证
对于输入 $3, 5, 7, 35, 105$：
| 菜肴对 | $\gcd$ | 互质？ | 美味度之和 |
|---|---|---|---|
| $(3, 5)$ | $1$ | ✓ | $8$ |
| $(3, 7)$ | $1$ | ✓ | $10$ |
| $(3, 35)$ | $1$ | ✓ | $38$ |
| $(3, 105)$ | $3$ | ✗ | — |
| $(5, 7)$ | $1$ | ✓ | $12$ |
| $(5, 35)$ | $5$ | ✗ | — |
| $(5, 105)$ | $5$ | ✗ | — |
| $(7, 35)$ | $7$ | ✗ | — |
| $(7, 105)$ | $7$ | ✗ | — |
| $(35, 105)$ | $35$ | ✗ | — |
互质对中的最大和为 $38$（选择 $3$ 和 $35$），与样例输出一致。
4. 复杂度分析
- 时间复杂度：枚举所有对 $O(n^2)$，每对计算 GCD 为 $O(\log V)$（$V$ 为美味度最大值），总体 $O(n^2 \log V)$。$n = 1000$，$V = 10^6$ 时约 $500000 \times 20 = 10^7$ 次运算，完全可以通过
- 空间复杂度：存储数组 $O(n)$
5. 注意事项
- 本题不需要先排序或做其他预处理，直接枚举即可
- 答案最大为 $10^6 + 10^6 = 2 \times 10^6$，
int类型足以存储 - 如果美味度为 $1$，它与任何数互质，这是一个特殊但无需特殊处理的情况
示例代码
双重循环枚举所有菜肴对，判断互质后更新最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
// 辗转相除法（欧几里得算法）求最大公约数
// 原理：gcd(a, b) = gcd(b, a % b)，当 b 为 0 时，gcd 即为 a
// 例如：gcd(35, 3) -> gcd(3, 35%3) -> gcd(3, 2) -> gcd(2, 3%2) -> gcd(2, 1) -> gcd(1, 2%1) -> gcd(1, 0) -> 返回 1
int gcd(int a, int b) {
while (b != 0) { // 当 b 不为 0 时，持续迭代
int t = a % b; // 保存 a 除以 b 的余数
a = b; // 用 b 覆盖 a
b = t; // 用余数覆盖 b，进入下一轮迭代
}
return a; // 当 b 为 0 时，a 就是最大公约数
}
int main() {
int n;
std::cin >> n; // 读入菜肴的个数
int v[1005]; // 存储每道菜肴的美味度，数组开大一点防止越界
for (int i = 0; i < n; i++) {
std::cin >> v[i]; // 依次读入每道菜肴的美味度
}
int ans = 0; // 用于记录满足互质条件的菜肴对中美味度之和的最大值
// 双重循环枚举所有不同的菜肴对 (i, j)
// 内层循环 j 从 i+1 开始，保证每对只枚举一次，避免重复
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 调用 gcd 函数判断两道菜肴的美味度是否互质
// 互质的定义：两数的最大公约数等于 1
if (gcd(v[i], v[j]) == 1) {
// 若互质，用两道菜肴的美味度之和与当前最大值比较，取较大者
ans = std::max(ans, v[i] + v[j]);
}
}
}
std::cout << ans << std::endl; // 输出互质菜肴对美味度之和的最大值
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
