题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。保证所有$a[i]$互不相同。

首先，你需要往$a$中添加一个不同于任何$a[i]$的数。

然后选定一个正整数$x$。每次操作，可以把一个$a[i]$增加$x$。

注意每次操作中的$x$都是一样的。使所有$a[i]$都相同，至少要操作多少次？

输入样例

3
3
1 2 3
5
1 -19 17 -3 -15
1
10

输出样例

6
27
1

算法

数学

一开始以为是$div3$的题，提交的时候发现是$EDU$的题目，怪不得这么难。可以发现存在一个最优解，就是让所有的数都加某个$x$，直到所有数都加成$max_{i \in [1,n]}a_i$。

那此时我们计算所有元素$a[i]$离这个目标值的距离$max_{i \in [1,n]}a_i-a_i$，这些距离的最大公约数就是$x$（这样可以使步长最大，让所有数变成目标值的步数最小），有了$x$就可以快速计算出原始数组$a$变得所有元素都相同最少需要操作多少次。接下来就可以考虑新加的这个数是多少，我们从$max_{i \in [1,n]}a_i$开始，每次减$x$，第一个不在$a$中的数就是这个新加的$a_{n+1}$。

至于如何快速判断某个数在不在$a$中，只需要把$a$中元素存到一个哈希集合中就可以了。

复杂度分析

时间复杂度

对数组$a$排序的时间复杂度为$O(nlog_2n)$。欧几里得算法求$x$需要对每个$a[i]$做一次$gcd$，时间复杂度为$O(nlogA)$，其中$A$为$a[i]$的值域。最后确定$a_n$，从$max_{i \in [0,n)}a[i]$开始尝试，当尝试的数不在集合$us$中就可以马上确定出来，在最差情况下$us$中有$O(n)$级别的元素个数，每个都对尝试的数做了一次排除，这时候确定出$a_n$的时间复杂度为$O(n)$。

综上，整个算法的时间复杂度为$O(n(log_2n+logA)+n)$。

空间复杂度

除去输入的数组$a$，哈希表的空间消耗为$O(n)$，这也是整个算法的额外空间复杂度。

$python$代码

from math import gcd

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if n == 1:
        print(1)
    else:
        a.sort()
        us = set(a)
        x = 0
        for num in a:
            x = gcd(x, a[-1] - num)
        ans = 0
        for num in a:
            ans += (a[-1] - num) // x
        k = 1
        while a[-1] - k*x in us:
            k += 1
        an = a[-1] - k*x
        ans += (a[-1] - an) // x
        print(ans)