《P17011 [GESP202606 五级] 晚宴》

题目描述小明去参加晚宴。晚宴中有 n 个菜肴每个菜肴都有一个美味度第 i 个菜肴的美味度为 vi​。晚宴规定小明只能恰好选取两道菜肴并且这两道菜肴的美味度必须要互质即最大公约数为 1。请帮助小明选取两道菜肴使得两道菜肴美味度之和最大。输入格式输入 2 行第一行为一个正整数 n表示菜肴的个数第二行为 n 个整数 v1​,v2​,⋯,vn​ 表示菜肴的美味度整数之间以空格分隔。输出格式输出一个整数表示两道互质菜肴美味度之和的最大值。输入输出样例输入 #1复制5 3 5 7 35 105输出 #1复制38说明/提示样例解释 1最优选择是 3 和 35。注意到105 与其他任意菜肴的最大公约数都大于 1因此无法参与合法选择。数据范围2≤n≤1000, 1≤vi​≤1000000。数据保证不存在相同美味度的菜肴。数据保证至少存在一种选取两道菜肴的方案。代码实现#include iostream #include vector #include algorithm using namespace std; int gcd(int a, int b) { while (b ! 0) { int tmp a % b; a b; b tmp; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint v(n); for (int i 0; i n; i) { cin v[i]; } int max_sum 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { int x v[i], y v[j]; if (gcd(x, y) 1) { max_sum max(max_sum, x y); } } } cout max_sum \n; return 0; }