OneCoder Avatar
OneCodercoderli.com · 1026 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++五级真题 luogu-P17011 [GESP202606 五级] 晚宴

📅 2026-07-07·✍️ OneCoder·计算中...·⏱️ 8 分钟

GESP C++五级2026年6月真题。本题考查最大公约数(GCD)与枚举,需要在所有互质的菜肴对中找出美味度之和的最大值。难度⭐⭐。本题在洛谷评定为普及-。

luogu-P17011 [GESP202606 五级] 晚宴

题目要求

题目描述

小明去参加晚宴。晚宴中有 个菜肴,每个菜肴都有一个美味度,第 个菜肴的美味度为 。

晚宴规定小明只能恰好选取两道菜肴,并且这两道菜肴的美味度必须要互质(即最大公约数为 )。

请帮助小明选取两道菜肴,使得两道菜肴美味度之和最大。

输入格式

输入 行,

第一行为一个正整数 ,表示菜肴的个数;

第二行为 个整数 表示菜肴的美味度,整数之间以空格分隔。

输出格式

输出一个整数,表示两道互质菜肴美味度之和的最大值。

输入输出样例 #1

输入 #1
PLAINTEXT2 行
5
3 5 7 35 105
输出 #1
PLAINTEXT1 行
38

说明/提示

最优选择是 和 。

注意到, 与其他任意菜肴的最大公约数都大于 ,因此无法参与合法选择。

数据范围

,。

数据保证不存在相同美味度的菜肴。

数据保证至少存在一种选取两道菜肴的方案。


题目分析

本题的核心是从 个菜肴中选取两道美味度互质()的菜肴,使得美味度之和最大。

1. 互质的判定

两个整数 、 互质,当且仅当 。可以用 辗转相除法(欧几里得算法) 高效计算最大公约数:

当 时,。C++ 中可以使用 __gcd() 函数或自行实现。

2. 枚举策略

数据范围 ,因此可以枚举所有的二元组 ,共 对,最多约 对。对每一对判断是否互质,若互质则更新答案。

具体步骤:

  1. 读入所有菜肴的美味度
  2. 双重循环枚举所有不同的菜肴对 (其中 )
  3. 对每一对计算 ,若结果为 ,则用 更新最大值
  4. 输出最大值

3. 样例验证

对于输入 :

菜肴对 互质? 美味度之和
✓
✓
✓
✗ —
✓
✗ —
✗ —
✗ —
✗ —
✗ —

互质对中的最大和为 (选择 和 ),与样例输出一致。

4. 复杂度分析

  • 时间复杂度:枚举所有对 ,每对计算 GCD 为 ( 为美味度最大值),总体 。, 时约 次运算,完全可以通过
  • 空间复杂度:存储数组

5. 注意事项

  • 本题不需要先排序或做其他预处理,直接枚举即可
  • 答案最大为 ,int 类型足以存储
  • 如果美味度为 ,它与任何数互质,这是一个特殊但无需特殊处理的情况

示例代码

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

C++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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!