202606-晚宴(luogu-P17011)

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

5
3 5 7 35 105

输出 #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$。可以用 辗转相除法（欧几里得算法） 高效计算最大公约数：

当 $b = 0$ 时，$\gcd(a, 0) = a$。C++ 中可以使用 __gcd() 函数或自行实现。

2. 枚举策略

数据范围 $n \le 1000$，因此可以枚举所有的二元组 $(i, j)$，共 $\frac{n(n-1)}{2}$ 对，最多约 $500000$ 对。对每一对判断是否互质，若互质则更新答案。

具体步骤：

1. 读入所有菜肴的美味度
2. 双重循环枚举所有不同的菜肴对 $(i, j)$（其中 $i < j$）
3. 对每一对计算 $\gcd(v_i, v_j)$，若结果为 $1$，则用 $v_i + v_j$ 更新最大值
4. 输出最大值

3. 样例验证

对于输入 $3, 5, 7, 35, 105$：

互质对中的最大和为 $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$，它与任何数互质，这是一个特殊但无需特殊处理的情况

示例代码

双重循环枚举所有菜肴对，判断互质后更新最大值。

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号