2026年6月GESP真题及题解（C++五级）：晚宴

题目描述

小明去参加晚宴。晚宴中有 $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

说明/提示

样例解释 1

最优选择是 $3$ 和 $35$。

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

数据范围

$2\le n\le 1000$, $1\le v_i\le 1000000$。

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

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

思路分析

题目要求从 $n$ 个美味度中恰好选两个，且这两个数互质（最大公约数为 1），使它们的和最大。
$n\le 1000$，直接枚举所有二元组 $(i,j)$，求 $\gcd (v_i,v_j)$，判断是否为 1，更新最大值即可。
总枚举量约 $5\times 10^5$，每次 $\gcd$ 为 $O(\log 10^6)$，总时间完全足够。

---

代码实现

#include <bits/stdc++.h>
using namespace std;
int n , v[1005]; 

// 求最大公约数
int g(int a,int b){
    if(b==0) return a;
    else return g(b,a%b);
} 

int main(){
    cin>>n; 
    for(int i=1;i<=n;i++) cin>>v[i]; 
    
    int ans=0; // 最大和
    for(int i=1;i<=n;i++){ // 枚举第一道菜
        for(int j=i+1;j<=n;j++){ // 枚举第二道菜
            if(g(v[i],v[j])==1){ // 互质
                int s=v[i]+v[j]; // 当前和
                if(s>ans) ans=s; // 更新答案
            }
        }
    }
    cout<<ans; // 输出结果
    return 0;
}

---

功能分析

• 输入：使用 cin 读取 $n$ 和 $n$ 个美味度。
• 处理：两层循环枚举所有不同的菜肴组合，通过自定义最大公约数函数 g 判断互质性，若互质则求和并维护最大值。
• 输出：使用 cout 输出最大合法和。
• 复杂度：时间复杂度 $O(n^2\log V)$（$V\le 10^6$），空间复杂度 $O(n)$。

---

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
	cout<<"##########  一站式掌握信奥赛知识!  ##########";
	cout<<"#############  冲刺信奥赛拿奖!  #############";
	cout<<"######  课程购买后永久学习，不受限制!   ######";
	return 0;
}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
	cout<<"跟着王老师一起学习信奥赛C++";
	cout<<"    成就更好的自己！       ";
	cout<<"  csp信奥赛一等奖属于你!   ";
	return 0;
}