Daimayuan Online Judge-整齐的数组
题目描述
\(Polycarp\) 有一个长度为 \(n\) 的数组 \(a_1,a_2,...,a_n\)(\(n\) 是偶数)。\(Polycarp\) 还得到了一个正整数 \(k\)，他开始对数组 \(a\) 做如下操作：选择一个下标 \(i(1≤i≤n)\) 使 \(a_i\) 减去 \(k\)。
在 \(Polycarp\) 进行若干次操作后(可能 \(0\) 次)，数组 \(a\) 中的所有数都变成相同的了。请你找到最大的符合要求的 \(k\)，如果 \(k\) 可以为任意大，请输出 \(−1\)。
输入格式
第一行一个整数 \(t\)，表示测试单元的个数。
接下来每个测试单元有两行。第一行包含一个偶数 \(n\)。第二行包含 \(n\) 个整数 \(a_1,a_2,...,a_n\)。
输出格式
对于每个测试单元输出单独一行一个整数 \(k(k≥1)\) —— \(Polycarp\) 能用来对数组进行操作的最大的数，或者 \(−1\) —— 如果 \(k\) 能任意大的话。
样例输入
3
6
1 5 3 1 1 5
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
样例输出
2
1
1100
数据范围
所有数据保证 \(1≤t≤10\)，\(4≤n≤40\)(\(n\) 是偶数)，\(−10^6≤a_i≤10^6\)，并且 \(n\) 的总和不超过\(100\)。
解题思路
我们需要对数组中的某些数减去若干个 \(k\)，比如数组中的 \(a[i]\) 和 \(a[j]\) 且 \(a[i]≤a[j]\)，并且 \(a[i] - n * k = a[j] - m * k\)，那么我们可以得到 \(a[i] = a[j] + (n - m) * k\)。经过操作，数组中的数都变成相同的，根据前面推导的式子也就相等于所有的数都变成了最小的那个数。我们只需要计算每个数与最小数的差值的最大公约数即可。特判所有数都相等时输出 \(-1\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50;
int t, n;
int a[N];
int gcd(int a, int b)
{
if(b == 0)
return a;
return gcd(b, a % b);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while(t --)
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
sort(a + 1, a + n + 1);
int ans = 0;
for(int i = 2; i <= n; i ++)
{
if(a[i] == a[1]) continue;
ans = gcd(ans, a[i] - a[1]);
}
if(ans) printf("%d\n", ans);
else puts("-1");
}
return 0;
}