题源链接：洛谷 P17011 [GESP202606 五级] 晚宴

---

一、背景

在算法竞赛的入门阶段，有一类问题看似简单，却暗藏"陷阱"——它们披着"找最大值"的外衣，却在最优解的路上设下了一道数学门槛。GESP 五级的这道晚宴题，就是一个典型代表。

题目说得很直白：从 $n$ 个菜肴中恰好选两道，要求它们的美味度之和最大，但附加了一个硬性约束——两道菜的美味度必须互质。这意味着你不能简单地挑出两个最大的数相加完事。比如样例中的 $35$ 和 $105$，虽然它们分别是最大的两个数，但 $\gcd (35,105)=35$，根本不满足互质条件。

这类问题的本质，是在一个全局最优的候选集中，用数学条件做二次筛选。本文就从这道晚宴题出发，聊聊枚举这个最朴素却最可靠的策略，以及欧几里得算法在背后起到的关键作用。

---

二、核心思想

2.1 为什么枚举在这里是"最优解"？

很多初学者看到"找最大和"，第一反应是排序后取前两个。但互质条件的存在，彻底打破了这种贪心思路。我们不妨把问题想象成一场"相亲配对"：

• 每个菜肴都是一个"候选人"
• 我们要找"最般配的一对"
• 但"般配"的标准不是简单的门当户对（数值大），而是有一个额外的硬性指标（互质）

在这种场景下，排序+贪心失效——因为前两名可能根本不满足互质条件，而第三名和第一名反而可能是天作之合。因此，唯一可靠的方法就是把所有可能的配对都看一遍，从中挑出满足条件且和最大的那一对。

枚举策略的特征：

• 完备性：不遗漏任何合法候选，保证找到全局最优
• 简单性：实现直观，代码量少，调试友好
• 可预测性：时间复杂度完全由数据规模决定，没有隐藏陷阱
• 适用边界：当 $n$ 较小（通常 $n\le 2000$）时，$O(n^2)$ 的枚举完全在可接受范围内

2.2 互质判定的核心：辗转相除法

判断两个数是否互质，本质上是计算它们的最大公约数（Greatest Common Divisor，GCD）。如果 $\gcd (a,b)=1$，则两数互质。

欧几里得算法（辗转相除法）是计算 GCD 的经典方法，它的核心思想非常优雅：

KaTeX parse error: Unexpected character: '' at position 24: …b) = \gcd(b, a ̲mod b)

直到余数为 $0$ 时，除数就是最大公约数。这个算法的时间复杂度是 $O(\log \min (a,b))$，效率极高。

我们可以把辗转相除法想象成不断"裁剪"两个矩形：

• 你有两个长度分别为 $a$ 和 $b$ 的线段
• 每次用较短的线段去量较长的线段，记录余数
• 重复这个过程，直到刚好量尽——此时短的那段长度，就是能同时整除两者的最大长度

在 C++ 中，标准库已经为我们提供了 __gcd(a, b) 函数（定义在 <algorithm> 中），可以直接调用。

2.3 去重与避免自配对

枚举菜对时，有一个容易忽略的细节：如何避免重复计算和自配对？

我们的做法是：外层循环 $i$ 从 $1$ 到 $n-1$，内层循环 $j$ 从 $i+1$ 到 $n$。这样每个无序对 $(a_i,a_j)$ 只会被访问一次，既不会重复，也不会出现 $i=j$ 的自配对情况。

这就像一个单向握手规则：第 $1$ 个人和第 $2,3,\dots ,n$ 个人握手；第 $2$ 个人只和第 $3,4,\dots ,n$ 个人握手（不再和第 $1$ 个人握，因为已经握过了）。总握手次数就是 KaTeX parse error: Unexpected character: ' ' at position 9: C_n^2 = ̲rac{n(n-1)}{2}。

---

三、算法模板

3.1 算法到底在干什么？——直觉解释

如果把所有菜对看作一个"候选池"，我们的算法就是在做三件事：

1. 生成候选：遍历所有不重复的菜对 $(i,j)$
2. 条件筛选：用 GCD 判断这对菜是否互质
3. 择优录取：在满足条件的菜对中，保留和最大的那个

整个过程就像一台自动筛选机：传送带把一对对菜肴送进来，机器检查它们是否互质，如果是，就和当前记录的最佳组合比一比，留下更强的那个。

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

function 枚举找最大互质和(a[1..n]):
    ans = 0
    for i = 1 to n-1:
        for j = i+1 to n:
            if gcd(a[i], a[j]) == 1:
                ans = max(ans, a[i] + a[j])
    return ans

实战代码（通用模板）：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;    // 根据题目数据范围设定

int n;
int a[N];
int ans;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // 枚举所有不重复的菜对
    for (int i = 1; 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;
}

3.3 例题实现 —— 本题完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;                // 常量：最大菜肴数量

int n;                             // n: 菜肴个数
int ans;                           // ans: 两道互质菜肴美味度之和的最大值
int a[N];                          // a[i]: 第 i 个菜肴的美味度

int main()
{
    cin >> n;                      // 读入菜肴个数

    for (int i = 1; i <= n; i++)  // 读入 n 个菜肴的美味度
        cin >> a[i];

    for (int i = 1; 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;
}

3.4 对比实现 —— 其他路径的探讨

虽然本题的数据规模使得 $O(n^2)$ 枚举完全够用，但在面试或更复杂的场景中，可能会遇到 $n$ 更大的情况。这里简单对比几种可能的优化思路：

方案	核心思想	时间复杂度	适用场景
双重枚举 + GCD（本题做法）	暴力遍历所有对	$O(n^2\log V)$	$n\le 2000$，实现简单
排序 + 双指针优化	按值排序后从大到小枚举	$O(n^2\log V)$（最坏）	需要剪枝时
质因数分解 + 容斥	预处理每个数的质因子，用容斥原理找互质对	$O(n\sqrt{V})$ 预处理	$n$ 很大（$10^5$ 级别）
哈希表优化	用桶记录数值出现次数，枚举因数配对	$O(V\log V)$	数值范围 $V$ 较小

对于 GESP 五级的数据范围（$n\le 1000$），双重枚举无疑是最清晰、最不容易出错的选择。

3.5 变体清单 —— 常见变形

变体类型	题目描述	关键变化	解法调整
选 $k$ 道互质菜	从 $n$ 道中选 $k$ 道，要求两两互质，和最大	$k$ 从 $2$ 变为任意	DFS/回溯枚举子集，配合 GCD 判断
不要求恰好两道	选任意数量（至少两道）互质菜，和最大	数量不固定	转化为最大独立集问题，或贪心+验证
互质改为倍数关系	选两道，要求一道是另一道的倍数	条件从 GCD 变为整除	排序后枚举，用倍数关系判断
带权互质	每道菜有权重，要求互质且权重和最大	目标函数变化	同上，仅比较对象改变
在线查询	多次查询，每次问某个子区间内的最大互质和	需要支持区间查询	莫队算法 + 离线处理，或线段树维护

3.6 什么时候不能用？——边界条件和反例

枚举策略虽然万能，但并非没有边界：

• $n$ 过大时：如果 $n=10^5$，$O(n^2)$ 的枚举将达到 $10^{10}$ 量级，必然超时。此时需要更高级的算法（如质因数分解 + 容斥）。
• 数值范围极大时：如果 $v_i$ 达到 $10^{18}$，__gcd 虽然仍是 $O(\log V)$，但需要注意数据类型使用 long long。
• 无解情况：题目保证有解吗？如果所有数两两不互质（比如全是偶数），则没有合法菜对。此时需要输出什么？本题未明确说明，实际竞赛中应仔细阅读题意，通常可以输出 $0$ 或特判。
• 贪心陷阱：如前文所述，不能简单地选两个最大的数。反例：$[6,10,15]$，最大两个是 $10$ 和 $15$，和为 $25$，但 $\gcd (10,15)=5$；而 $6$ 和 $15$ 互质，和为 $21$。如果 $[35,105,7]$，最大两个 $35+105=140$ 不互质，正确答案应为 $35+7=42$ 或 $105+7=112$。

---

四、底层逻辑

4.1 为什么枚举一定能找到正确答案？

这是一个关于完备性的证明。假设最优解是菜对 $(v_p,v_q)$，其中 $1\le p<q\le n$。在我们的双重循环中：

• 外层循环 $i$ 会取到 $p$
• 当 $i=p$ 时，内层循环 $j$ 会取到 $q$（因为 $j$ 从 $i+1$ 遍历到 $n$）
• 此时会检查 $\gcd (v_p,v_q)$，如果等于 $1$，就会用 $v_p+v_q$ 更新 $ans$

由于我们遍历了所有满足 $i<j$ 的无序对，最优解必然会被访问到。只要最优解满足互质条件，它就会被纳入候选并参与最大值的比较。因此，算法一定能找到正确答案。

4.2 与经典问题的对比

这道题和经典的"两数之和"问题有相似之处，但约束条件不同：

问题	目标	约束	典型解法
两数之和	找和为 target 的一对数	无特殊数学约束	哈希表 $O(n)$
最大和子数组	找连续子数组的最大和	连续性约束	动态规划 / 贪心 $O(n)$
本题：最大互质和	找互质的一对数的最大和	互质约束	枚举 $O(n^2\log V)$

可以看到，互质约束是一个非单调、非局部的条件，无法通过排序或哈希等线性方法直接处理，这也是为什么枚举成为本题的自然选择。

4.3 隐含约束的分析

题目中有一个容易被忽略的细节：“恰好选取两道菜肴”。这意味着：

• 不能选一道（即使那道菜再大也不行）
• 不能选三道或更多
• 两道必须是不同的菜肴（$ieqj$）

我们的代码通过 $j$ 从 $i+1$ 开始，自然保证了 $ieqj$。而"恰好两道"则意味着我们不需要考虑选更多菜的情况，简化了问题。

---

五、决策表

面对"从集合中选出满足某数学条件的元素，使目标函数最优"这类问题，如何快速选型？

场景特征	推荐方案	时间复杂度	备注
$n\le 2000$，条件涉及两元素关系	双重枚举	$O(n^2)$	最稳妥，代码简洁
$n\le 10^5$，条件可转化为数值范围查询	排序 + 双指针 / 二分	$O(n\log n)$	需要条件具有单调性
条件涉及 GCD / LCM，数值范围小	质因数分解 + 桶 / 容斥	$O(V\log V)$ 或 $O(n\sqrt{V})$	$V$ 为数值最大值
多次查询，集合动态变化	线段树 / 树状数组维护	$O(\log n)$ 每次查询	需要设计合适的合并操作
需要选 $k$ 个元素（$k>2$）	DFS / 回溯 / 状态压缩 DP	指数级或 $O(2^n)$	$k$ 和 $n$ 都不能太大

一句话总结：数据规模小，枚举为王；数据规模大，先想数学性质，再选数据结构。

---

六、工程视角

枚举 + GCD 的思想在实际工程中有着广泛的应用：

1. 密码学与 RSA 算法：RSA 的核心依赖于选择两个大质数 $p$ 和 $q$，使得它们互质于 KaTeX parse error: Unexpected character: '' at position 1: ̲arphi(n)。GCD 的计算是密钥生成和验证的基础操作。

2. 分数约简与有理数运算：在图形渲染、金融计算等领域，经常需要处理分数。判断两个分数能否约简、找最简公分母，都离不开 GCD。例如，将 KaTeX parse error: Unexpected character: ' ' at position 1: ̲rac{12}{18} 约简为 KaTeX parse error: Unexpected character: ' ' at position 1: ̲rac{2}{3}，本质就是计算 $\gcd (12,18)=6$。

3. 任务调度与资源分配：在操作系统中，多个进程共享资源时，可能需要判断它们的资源需求是否"互质"（即没有共同的冲突因子），从而决定能否并行执行。枚举所有可能的调度组合并筛选可行方案，是调度算法的常见思路。

4. 哈希表设计：在设计哈希函数时，表长 $m$ 通常选为质数，或确保与键的分布因子互质，以减少冲突。GCD 在这里用于分析哈希函数的均匀性。

---

七、小结

本文从一道 GESP 五级真题出发，探讨了枚举与最大公约数这对经典组合。

核心认知可以总结为：

当"最优"被附加了不可贪心的数学约束时，枚举是最诚实的策略；而 GCD 则是处理整数关系时最基础、最高效的数学工具。

用公式化的语言概括：

e x t 答案 = max ⁡ 1 ≤ i < j ≤ n { v i + v j ∣ gcd ⁡ ( v i , v j ) = 1 } ext{答案} = \max_{1 \leq i < j \leq n} \{v_i + v_j \mid \gcd(v_i, v_j) = 1\} ext答案=1≤i<j≤nmax​{vi​+vj​∣gcd(vi​,vj​)=1}

这道题教会我们的，不仅是如何写双重循环和调用 __gcd，更是一种面对约束时的思维习惯：先判断约束是否破坏贪心性质，再决定是否需要枚举验证。在算法竞赛中，这种"先想性质，再选策略"的思维路径，比记住某个具体算法更重要。

---

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题欢迎在评论区留言交流。

标签： #GESP #算法竞赛 #枚举 #最大公约数 #欧几里得算法 #C++ #洛谷 #入门算法