题目描述

难度分:$1200$

输入$T(\leq 500)$表示$T$组数据。每组数据输入$n(2 \leq n \leq 100)$和长为$n$的数组$a(1 \leq a[i] \leq 10^{17})$。保证所有$a[i]$互不相同。

找到一个在$[1,10^{18}]$中的$k$，使得所有$a[i]=a[i] \% k$后，$a$中恰好有两个不同的数。

输出这个$k$。如果有多个答案，输出任意一个。可以证明，答案是存在的。

输入样例

5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1

输出样例

7
30
3
5000
1000000000000000000

算法

枚举

先考虑一个简单情况，如果$a$数组既有奇数又有偶数，那么答案就是$2$。

否则分析性质，我们发现对一个数模上$2^b$其实就是保留其二进制的最后$b+1$位。所以$k=4$开始，检查是否合法，合法就输出$k$，不合法就倍增$k$。由于$a$中所有元素都不相同，必然会存在一个$k$，使得保留的二进制后缀刚好是两个不同的数。

复杂度分析

时间复杂度

$k$的尝试次数就是$a$中最大值取$log$之后的级别，时间复杂度为$O(log_2max(a)$。而每尝试一个$k$，就要遍历$a$数组检查一下是不是只有两个取模之后的结果，时间复杂度为$O(n)$。因此，整个算法的时间复杂度为$O(nlog_2max(a))$。

空间复杂度

空间消耗在于每检查一个$k$是否合法时，需要一个集合来保存$a[i] \% k$的结果。在最差情况下可能每个元素模$k$的结果都不相同，空间复杂度为$O(n)$。

$python$代码

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    def check(k):
        b = set()
        for ai in a:
            b.add(ai % k)
        return len(b) == 2

    cnt0, cnt1 = 0, 0
    for ai in a:
        if ai&1:
            cnt1 += 1
        else:
            cnt0 += 1
    if cnt0 > 0 and cnt1 > 0:
        print(2)
    else:
        if n == 2:
            print(max(a))
        else:
            k = 4
            while 1:
                if check(k):
                    print(k)
                    break
                k <<= 1