G5024 [GESP202606 五级] 晚宴 题解

知识点：双重枚举、最大公约数、最值。

解题思路

枚举不同下标对，若两数最大公约数为1，就用它们的和更新最大值。

为什么正确

所有可选二人组合恰枚举一次，互质筛选保证合法，取最大和得到最优。

易错点

相同下标不能配对；没有合法组合时按题目输出0。

复杂度

时间O(n² log A)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    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;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。