A. Kamilka and the Sheep 详细题解

一、问题重述

有 $n$ 只羊，每只羊有初始美貌值 $a_i$（互不相同）。你可以选择一个非负整数 $d$，使每只羊的美貌值增加 $d$。然后选择两只羊，其美貌值为 $x$ 和 $y$，愉悦度为 $\gcd(x, y)$。求最大可能的愉悦度。

---

二、核心观察

2.1 关键公式

对于任意两个正整数 $x < y$，有：

$$\gcd(x, y) = \gcd(x, y - x)$$

因此 $\gcd(x, y)$ 不会超过 $y - x$。

2.2 上界分析

设最终选择的两只羊的美貌值（加上 $d$ 后）为 $x$ 和 $y$（$x < y$），则：

$$\gcd(x, y) \le y - x \le (\max(a_i) + d) - (\min(a_i) + d) = \max(a_i) - \min(a_i) $$

所以最大可能的愉悦度不可能超过 $\max(a_i) - \min(a_i)$。

2.3 构造达到上界

取 $d = (-\min(a_i)) \bmod (\max(a_i) - \min(a_i))$，即：

$$d = \left( \max(a_i) - \min(a_i) - \min(a_i) \bmod (\max(a_i) - \min(a_i)) \right) \bmod (\max(a_i) - \min(a_i)) $$

更简单：选择 $d$ 使得 $\min(a_i) + d$ 是 $\max(a_i) - \min(a_i)$ 的倍数。

设 $m = \max(a_i) - \min(a_i)$。令 $d = m - (\min(a_i) \bmod m)$，则：

• $\min(a_i) + d$ 是 $m$ 的倍数
• $\max(a_i) + d = \min(a_i) + m + d$ 也是 $m$ 的倍数

因此：

$$\gcd(\min(a_i) + d, \max(a_i) + d) = m$$

即可以达到上界 $\max(a_i) - \min(a_i)$。

---

三、结论

答案即为：

$$\boxed{\max(a_i) - \min(a_i)}$$

---

四、标程代码

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    cout << a[n - 1] - a[0] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

---

五、示例验证

示例 1：$[1, 3]$

• $\max - \min = 2$，输出 $2$ ✅

示例 2：$[5,4,3,2,1]$

• $\max - \min = 5 - 1 = 4$，输出 $4$ ✅

示例 3：$[5,6,7]$

• $\max - \min = 2$，输出 $2$ ✅

示例 4：$[1,11,10]$

• $\max - \min = 11 - 1 = 10$，输出 $10$ ✅

---

六、复杂度分析

• 排序 $O(n \log n)$，$n \le 100$，完全可行
• 也可直接找最大值和最小值 $O(n)$

---

七、总结

这道题的关键是利用 $\gcd(x, y) = \gcd(x, y - x)$ 得到上界 $\max(a) - \min(a)$，然后通过构造 $d$ 证明这个上界可以达到。因此答案非常简单：最大值与最小值的差。