题意
给你一个整数数组 $a_1, a_2, \dots, a_n$ ,它的所有元素都是不同的。
首先,要求你在这个数组中再插入一个整数 $a_{n+1}$ 。 $a_{n+1}$ 不应等于 $a_1, a_2, \dots, a_n$ 中的任何一个。
然后,您必须使数组中的所有元素相等。开始时,您选择一个正整数 $x$。在一次操作中,你将 $x$ 恰好添加到数组的一个元素中。注意 $x$ 在所有操作中都是一样的。
在你选择了 $a_{n+1}$ 和 $x$ 之后,要使所有元素相等所需的最小运算次数是多少?
题解
由于 $x$ 只能是正值,所以我们只能使所有元素等于数组中当前的最大值。
考虑不添加 $a_{n + 1}$。我们设 $a$ 中最大值为 $M$,则要想要运算次数最少,则需要使 $x$ 尽可能大,所以 $x$ 应该取 $gcd\{a_n -a_1, a_n-a_2, \dots, a_n-a_{n-1}\}$,然后直接枚举统计答案即可。
考虑添加 $a_{n+1}$。我们不希望改变 $x$(将会增加至少 $n$ 的答案),所以我们选择当 $a_{n+1} = M - k \cdot x$ 时 $k$($k > 0$) 使 $k$ 尽量小,且不与 $a$ 中元素重复。
Code:
#include <algorithm>
#include <iostream>
#include <map>
#pragma GCC optimize (3)
using namespace std;
typedef long long ll;
const int maxn = 200010;
int t;
ll ans, a[maxn], x;
int n;
map <ll, bool> p;
int main () {
ios::sync_with_stdio (false);
cin.tie (0);
cin >> t;
while (t--) {
cin >> n;
p.clear ();
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[a[i]] = true;
}
sort (a + 1, a + n + 1);
x = a[n] - a[1];
ans = 0;
for (int i = 2; i < n; i++) {
x = __gcd (x, a[n] - a[i]);
}
x = max (x, 1ll);
for (int i = 1; i < n; i++) ans += (a[n] - a[i]) / x;
for (ll i = a[n]; ; i -= x) {
if (!p[i]) {ans += (a[n] - i) / x; break;}
}
cout << ans << '\n';
}
return 0;
}