D1. All are Same - 题解

比赛与标签

比赛: Codeforces Round 748 (Div. 3) 标签: math, number theory 难度: *1100

题目大意喵~

一位叫做 Polycarp 的先生有一个整数数组 a，里面有 n 个数字。他还想好了一个正整数 k。

他可以对数组进行一种操作：选择任意一个元素 a_i，然后把它变成 a_i - k。这个操作可以进行任意多次。

经过若干次操作后，数组里所有的数都变得一模一样了！我们的任务就是找到能实现这个目标的、最大的正整数 k 是多少。如果 k 可以是任意大的数，那就输出 -1 呐。

简单来说，就是：

输入: 一个整数数组 a。
操作: a_i = a_i - k，k 是一个固定的正整数。
目标: 让数组所有元素相等。
输出: 最大的 k，或者 -1。

解题思路喵~

这道题看起来有点复杂，但只要我们抓住核心，就会发现它其实是一只很温顺的小猫咪哦！喵~

首先，我们来想想最后的状态。假设经过一顿操作猛如虎，数组里所有的元素都变成了同一个值，我们叫它 c 好了。

对于原来的任意一个元素 a_i，它之所以能变成 c，肯定是减了若干次 k 的结果。也就是说，对于每个 a_i，都存在一个非负整数 m_i（代表减了多少次 k），满足下面的式子： a_i - m_i * k = c

这个式子对数组里所有的元素都成立。现在我们随便拿出两个元素 a_i 和 a_j 来看：

a_i = c + m_i * k
a_j = c + m_j * k

把这两个式子相减，会发生什么奇妙的事情呢？ a_i - a_j = (c + m_i * k) - (c + m_j * k) = (m_i - m_j) * k

哇！看呐！a_i 和 a_j 的差，正好是 k 的整数倍！因为 m_i 和 m_j 都是整数，所以它们的差也是整数。

这个结论太重要啦！它告诉我们，k 必须是原数组中任意两个元素之差的公约数。

既然我们要找最大的 k，那 k 自然就应该是所有这些差的最大公约数 (GCD) 啦！也就是 k = gcd(|a_1 - a_2|, |a_1 - a_3|, ..., |a_{n-1} - a_n|)。

但是，计算所有数对的差再求 GCD，也太麻烦了的说！( ´•̥̥̥ω•̥̥̥ ) 别担心，这里有一个 GCD 的小技巧：gcd(x, y, z)和gcd(x, y-x, z-x)` 是一样的！推广一下，所有数对差的 GCD，其实就等于所有元素与某一个固定元素之差的 GCD。

比如说，我们可以把所有元素都和第一个元素 a[0] 作比较，那么我们要求的 k 就是： k = gcd(|a[1] - a[0]|, |a[2] - a[0]|, ..., |a[n-1] - a[0]|) 这样计算量就小多啦！

最后，还有一个特殊情况要考虑哦！如果一开始数组里所有的数就完全相同了呢？比如 [5, 5, 5, 5]。这时，任意两个元素的差都是 0。gcd(0, 0, ...) 在数学上没有约束力，这意味着 k 可以是任何正整数！因为我们根本不需要进行任何操作，数组就已经满足条件了。既然 k 可以无限大，按照题目要求，我们就应该输出 -1。

所以，我们的解题步骤就是：

检查数组中的所有元素是否已经相同。如果是，输出 -1。
如果不是，计算 gcd(|a[1]-a[0]|, |a[2]-a[0]|, ..., |a[n-1]-a[0]|)。
输出这个 GCD 就好啦！

代码实现喵！

下面就是把我们的思路变成代码的样子啦，我已经加上了详细的注释，希望能帮到你！

cpp

#include <iostream>
#include <vector>
#include <numeric> // std::gcd 在这里面哦
#include <cmath>   // std::abs 在这里面
#include <set>     // 用 set 来快速判断元素是否都相同

// 这个函数处理单个测试用例的说
void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    std::set<long long> distinct_elements; // 用集合来存放不同的元素
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        distinct_elements.insert(a[i]);
    }

    // 如果集合的大小是 1，说明所有元素都相同
    // 这种情况下，k 可以是任意大的正整数，所以输出 -1
    if (distinct_elements.size() == 1) {
        std::cout << -1 << std::endl;
        return;
    }

    // 核心思路：如果所有元素 a_i 都能通过减 k 变成 c，
    // 那么 a_i = c + m_i * k，a_j = c + m_j * k。
    // 两式相减得到 a_i - a_j = (m_i - m_j) * k。
    // 这说明 k 必须是任意两元素差的公约数。
    // 为了让 k 最大，k 必须是所有差的绝对值的最大公约数 (GCD)。

    // GCD 有个性质：gcd(|a_i - a_j|) 等于 gcd(|a_1-a_0|, |a_2-a_0|, ...)。
    // 这样我们只需要 O(n) 次计算，而不是 O(n^2) 次。
    
    long long result_gcd = 0;
    // 我们将所有元素与第一个元素 a[0] 的差的绝对值来计算 GCD
    for (int i = 1; i < n; ++i) {
        long long diff = std::abs(a[i] - a[0]);
        // std::gcd(0, x) 会返回 |x|，所以把 result_gcd 初始化为 0 是个很棒的技巧！
        // 第一次循环 result_gcd = gcd(0, |a[1]-a[0]|) = |a[1]-a[0]|
        // 之后就不断和新的差值求 GCD
        result_gcd = std::gcd(result_gcd, diff);
    }
    
    // 这样求出的 result_gcd 就是最大的 k 啦！
    // 因为我们可以把所有元素都减到 min(a) 或者更小的值，
    // 并且 (a_i - min(a)) 一定是 k 的倍数。
    std::cout << result_gcd << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(N log V) 的说。其中 N 是数组元素的个数，V 是数组中元素差的最大值。我们遍历一次数组来计算 GCD，循环 N-1 次。每次 std::gcd 的计算时间大约是 O(log V)。用 std::set 检查元素是否唯一的时间是 O(N log N)。因为 N 很小（最大40），所以总的时间非常快！
空间复杂度: O(N) 的说。我们用了一个 std::vector 来存储数组，还需要一个 std::set 来存储不同的元素，在最坏情况下它们都需要 O(N) 的空间。

知识点与总结喵~

这道题真是太棒了，让我们学到了好多东西！

问题转化: 最重要的能力就是把 "通过减 k 变成相同" 这个操作，转化为 "任意两元素之差是 k 的倍数" 这个数学模型。这是解题的关键一步！
最大公约数 (GCD): 看到 "公约数"、"最大"，就要立刻想到 GCD！它是解决这类问题的有力武器。
GCD 的性质: GCD({|a_i - a_j|}) = GCD({|a_i - a_k|}) 这个性质非常实用，能大大降低计算复杂度，是算法优化的好帮手。
边界处理: 不要忘记处理 "所有元素一开始就相同" 的特殊情况哦！这是决定你能否 AC 的小细节。用 std::set 来判断非常优雅。

希望我的讲解对你有帮助呐！只要我们勤于思考，把问题一步步分解，再难的题目也会变得清晰起来。继续加油，你一定可以成为算法大师的！喵~ (ฅ'ω'ฅ)

D1. All are Same - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

代码实现喵！ ​

复杂度分析的说 ​

知识点与总结喵~ ​