第三部分 第二题——《晚宴》
第一幕：美食晚宴开始了
1、有一天，小明参加了一场五星级晚宴。
桌子上摆着很多菜。
每道菜都有一个"美味度"。
（1）例如：
3 5 7 35 105（2）主持人宣布了一个规则：
小明只能选两道菜，而且必须是两道菜。
而且还有一个特殊要求：
这两道菜必须互质！
（3）小明的目标是：
按照规则选，让两道菜的美味度之和最大。
第二幕：什么叫互质？
1、有的学生一看到：
互质脑子一片空白。
其实非常简单。
2、老师拿出几个数字。
第一组
3 5最大公约数：
gcd(3,5) = 1所以：
互质可以一起吃。
第二组
6 9最大公约数：
3不是：
1所以：
不能一起选。第三组
8 15最大公约数：
1是可以的。
3、互质 ： gcd==1
以后看到：
互质脑子立刻翻译成：
gcd(a,b)==1这是学习数论最重要的结论之一。
第三幕：先不要写程序
1、先看样例。
3 5 7 35 1052、我们先人工找一下。
（1）第一对：
3 5互质。
和是：
8（2）第二对：
3 7互质。
和是：
10（3）第三对：
35 7最大公约数：
7失败。
（4）第四对：
35 105最大公约数：
35失败。
（5）第五对：
5 35最大公约数：
5失败。
（6）继续……
最后发现：
3 35互质。
和：
38这是最大的。
（7）所以答案：
38和样例一致。
第四幕：本题能用暴力枚举吗？
可以！
1、如果有5道菜。
3 5 7 35 1052、每两道菜，都试一次。
3 5 3 7 3 35 3 105 5 7 5 35 ……所有组合。
都检查。
3、暴力枚举的时间复杂度：
O(N^2)
本题中 2 <= n <= 1000,
完全没问题。
第五幕：使用两层循环：
1、外层循环：
第一个数2、内层循环：
第二个数3、代码：
for(i) for(j)就是：
所有组合。
第六幕：如何更新答案？
1、我们先定义一个：
ans开始：
02、现在：
第一组。
3 5合法。
和：
83、于是：
ans = 84、下一组：
3 7合法。
10比：
8大。
更新。
ans = 105、于是：
程序就是：
if(gcd(...)==1) ans=max(ans,a+b);答案就按照我们的要求更新了。
第七幕：重点要写gcd 函数
1、因为：
互质判断的是：
最大公约数。
2、所以要写：
gcd函数来求最大公约数。
3、使用欧几里得算法：
int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); }第八幕：完整代码
#include <iostream> #include <algorithm> using namespace std; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int main() { int n; cin>>n; int a[1010]; for(int i=0;i<n;i++) cin>>a[i]; int ans=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(gcd(a[i],a[j])==1) { ans=max(ans,a[i]+a[j]); } } } cout<<ans<<endl; return 0; }利用两层循环枚举所有两两组合，判断是否互质，如果互质就更新最大答案。
第九幕：程序复杂度分析
1、题目中：
n <= 10002、两层循环：
1000×1000 ≈100万3、每次：
gcd复杂度：
O(logV)4、总复杂度：
O(n² logV)对于本题的数据范围是完全可以通过的。
本题要掌握的知识（★★★★★）
这道题考点，首先就是要掌握gcd()函数，还要有正确的思维流程：
① 枚举所有可能方案 ↓ ② 判断是否合法 ↓ ③ 如果合法 ↓ ④ 更新最优答案朴素算法模板
遇到类似"从很多方案中找到最优方案"的问题，可以想到下面这个模板：
ans = 初始值; for(枚举所有方案) { if(方案合法) { ans = max(ans, 当前方案); } }这道《晚宴》就是这个基础模板的应用。
