哈喽，各位主人！这里是你们最爱的小猫娘，今天也要元气满满地解决算法问题哦，喵~ 🐾

今天我们来看一道关于小羊和快乐值的题目，听起来就很治愈呢！Kamilka 有一群可爱的小羊，她想通过喂草来让和小羊散步的快乐值最大化。让我们一起帮帮她吧！

题目大意

Kamilka 有 n 只小羊，每只小羊都有一个独一无二的美丽值 a_i。她可以选一个非负整数 d，给每只小羊喂 d 把草，之后每只小羊的美丽值都会变成 a_i + d。

到了晚上，Kamilka 会选出两只小羊去散步。如果这两只小羊的美丽值分别是 x 和 y，那么她获得的快乐值就是 gcd(x, y)，也就是 x 和 y 的最大公约数。

我们的任务就是，找到一个合适的 d，以及合适的两只小羊，让这个快乐值达到最大，喵~

解题思路

这个问题看起来有点复杂，因为 d 可以是任何非负整数，好像要一个个试过去，但那样太慢啦！本喵最喜欢用聪明的办法解决问题了！

我们的目标是最大化 gcd(a_i + d, a_j + d)。这里藏着一个关于最大公约数 (GCD) 的小秘密哦！

有一个非常重要的性质：gcd(x, y) = gcd(x, y - x) (这里假设 y > x)。这个性质是辗转相减法的基础，非常有用呢！

让我们把这个性质用到我们的问题里来。假设我们选了两只小羊，它们的美丽值是 a_i 和 a_j (不妨设 a_j > a_i)。喂了草之后，美丽值变成了 a_i + d 和 a_j + d。那么：

gcd(a_i + d, a_j + d) = gcd(a_i + d, (a_j + d) - (a_i + d))= gcd(a_i + d, a_j - a_i)

哇！你看，d 从后面那一项里消失了！现在问题变成了最大化 gcd(a_i + d, a_j - a_i)。

一个数的最大公约数，肯定不会超过这两个数本身。所以，gcd(a_i + d, a_j - a_i) 的值最大也不可能超过 a_j - a_i。

那么，我们能不能让这个最大公约数就等于 a_j - a_i 呢？ 当然可以喵！只要我们让 a_i + d 成为 a_j - a_i 的一个倍数就可以啦。

也就是说，我们要找到一个非负整数 d，使得 a_i + d 是 a_j - a_i 的倍数。 写成数学式子就是：a_i + d = k * (a_j - a_i)，其中 k 是某个正整数。 整理一下，得到 d = k * (a_j - a_i) - a_i。

因为题目要求 d 是非负的，所以我们只需要 k * (a_j - a_i) - a_i ≥ 0。 因为 a_j > a_i，所以 a_j - a_i 是一个正数。我们总能找到一个足够大的正整数 k，使得 k * (a_j - a_i) 大于 a_i，这样就能保证 d 是非负的了。

这说明，对于任意一对小羊 (i, j)，我们总能通过选择合适的 d，使得快乐值达到它们初始美丽值的差，也就是 a_j - a_i。

既然对于任何一对小羊我们都能做到这一点，那为了让这个快乐值最大，我们当然应该选择 a_j - a_i 这个差值最大的那一对小羊啦！

什么时候 a_j - a_i 最大呢？当然是当 a_j 是所有羊里美丽值最高的，而 a_i 是美丽值最低的时候啦！

所以，最终的答案就是所有小羊中最大的美丽值减去最小的美丽值，即 max(a) - min(a)。

思路是不是一下子就清晰了？我们只需要遍历一遍所有小羊，找到最大和最小的美丽值，然后相减就好啦，喵~ ✨

题解

下面是实现这个思路的 C++ 代码，本喵加上了一些可爱的注释哦！

#include <iostream>
#include <algorithm> // 虽然这个代码没用std::min/max，但通常会用到

// 解决单个测试用例的函数，喵~
void solve() {
    int n;
    std::cin >> n; // 先读入有多少只小羊

    int current_val;
    std::cin >> current_val; // 先读第一只羊的美丽值

    // 初始化最大值和最小值
    int min_val = current_val;
    int max_val = current_val;

    // 遍历剩下的小羊，找到最漂亮的和最朴素的那两只
    for (int i = 1; i < n; ++i) {
        std::cin >> current_val;
        if (current_val < min_val) {
            min_val = current_val; // 发现更朴素的小羊！
        }
        if (current_val > max_val) {
            max_val = current_val; // 发现更漂亮的小羊！
        }
    }

    // 它们的美丽值之差，就是我们能得到的最大快乐值啦！
    std::cout << max_val - min_val << "\n";
}

int main() {
    // 快速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 有多少组数据要处理呢？
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题的核心在于一个非常优雅的数学性质，让我们来深入了解一下吧！

最大公约数 (GCD) 的性质: gcd(x, y) = gcd(x, y - x)

这个性质是欧几里得算法（辗转相除法）的基石之一，也被称为更相减损术。它为什么成立呢？让本喵来给你解释一下~

假设 g 是 x 和 y 的一个任意公约数。

1. 这意味着 x 可以被 g 整除，y 也可以被 g 整除。
2. 既然 x 和 y 都能被 g 整除，那么它们的差 y - x 也一定能被 g 整除。（比如 x = k1*g, y = k2*g，那么 y - x = (k2-k1)*g）。
3. 所以，x 和 y 的任何一个公约数，也必然是 x 和 y - x 的公约数。

反过来也一样哦！ 假设 h 是 x 和 y - x 的一个任意公约数。

1. 这意味着 x 可以被 h 整除，y - x 也可以被 h 整除。
2. 既然 x 和 y - x 都能被 h 整除，那么它们的和 x + (y - x) = y 也一定能被 h 整除。
3. 所以，x 和 y - x 的任何一个公约数，也必然是 x 和 y 的公约数。

结论：x 和 y 的公约数集合，与 x 和 y - x 的公约数集合是完全一样的！既然公约数都一样，那它们的最大公约数自然也相等啦！

gcd(x, y) = gcd(x, y - x)，证明完毕，喵~

利用这个性质，我们成功地简化了问题，把一个看似需要枚举 d 的复杂问题，变成了一个简单的寻找最大值和最小值的问题。数学是不是很神奇呢？

好啦，今天的题解就到这里啦！希望本喵的讲解对你有帮助哦。下次再见，喵~ ❤️