A18397. 晚宴
填空题
困难
知识点
题目描述
晚宴
题目描述
小明去参加晚宴。晚宴中有 n 个菜肴，每个菜肴都有一个美味度，第 i 个菜肴的美味度为 vi。
晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质 (即最大公约数为 1)。
请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。
输入格式
输入两行，
第一行为一个正整数 n，表示菜肴的个数；
第二行为 n 个整数 v1,v2,...,vn 表示菜肴的美味度，整数之间以空格分隔。
输出格式
输出一个整数，表示两道互质菜肴美味度之和的最大值。
输入样例
5
3 5 7 35 105输出样例
38样例解释
最优选择是 3 和 35。
注意到，105 与其他任意菜肴的最大公约数都大于 1，因此无法参与合法选择。
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int arr[1010];
int main() {
int n;
cin >> n;
for (int i = 0, x; i < n; ++i)
cin >> arr[i];
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (gcd(arr[i], arr[j]) == 1)
ans = max(ans, arr[i] + arr[j]);
cout << ans << endl;
return 0;
}
上一题
下一题