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输入 15 3 5 7 35 105输出 138说明/提示样例解释 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)总时间完全足够。代码实现#includebits/stdc.husingnamespacestd;intn,v[1005];// 求最大公约数intg(inta,intb){if(b0)returna;elsereturng(b,a%b);}intmain(){cinn;for(inti1;in;i)cinv[i];intans0;// 最大和for(inti1;in;i){// 枚举第一道菜for(intji1;jn;j){// 枚举第二道菜if(g(v[i],v[j])1){// 互质intsv[i]v[j];// 当前和if(sans)anss;// 更新答案}}}coutans;// 输出结果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)。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}