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

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

题目描述

小明去参加晚宴。晚宴中有n nn个菜肴，每个菜肴都有一个美味度，第i ii个菜肴的美味度为v i v_ivi​。

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

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

输入格式

输入2 22行，

第一行为一个正整数n nn，表示菜肴的个数；

第二行为n nn个整数v 1 , v 2 , ⋯ , v n v_1, v_2, \cdots, v_nv1​,v2​,⋯,vn​表示菜肴的美味度，整数之间以空格分隔。

输出格式

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

输入输出样例 1

输入 1

5 3 5 7 35 105

输出 1

38

说明/提示

样例解释 1

最优选择是3 33和35 3535。

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

数据范围

2 ≤ n ≤ 1000 2 \le n \le 10002≤n≤1000,1 ≤ v i ≤ 1000000 1 \le v_i \le 10000001≤vi​≤1000000。

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

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

思路分析

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

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,v[1005];// 求最大公约数intg(inta,intb){if(b==0)returna;elsereturng(b,a%b);}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>v[i];intans=0;// 最大和for(inti=1;i<=n;i++){// 枚举第一道菜for(intj=i+1;j<=n;j++){// 枚举第二道菜if(g(v[i],v[j])==1){// 互质ints=v[i]+v[j];// 当前和if(s>ans)ans=s;// 更新答案}}}cout<<ans;// 输出结果return0;}

功能分析

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

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

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

【秘籍汇总】（完整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>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}