CF1305F Kuroni and the Punishment
不难发现答案上界为 \(n\)。
考虑我们能做什么？我们可以对一个 gcd 快速求出最少操作次数。
这启发我们将 gcd 确定在某个范围后暴力对每个 gcd 做上面的操作。
gcd 怎么来？从 \(a\) 中来。如果确定 \(a_i\) 的最终值，那么 gcd 一定是其质因子。
\(a_i\) 的最终值难以确定，但是我们有很多尝试的机会，注意到 \(a_i\) 增减一或不变的个数至少为 \(\lceil\frac{n}{2}\rceil\)。只要知道其中一个就行了，直接随机就做完了。
做法很简单，但是很巧妙。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T, typename... Rest>
inline void read(T &x, Rest&... rest) {
read(x), read(rest...);
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 2e5 + 10;
int n;
LL a[N];
vector<LL> vec;
void div(LL n) {
for(LL i = 2; i * i <= n; ++i)
if(n % i == 0) {
vec.emplace_back(i);
while(n % i == 0)
n /= i;
}
if(n > 1) vec.emplace_back(n);
}
int solve(LL x) {
LL ans = 0;
for(int i = 1; i <= n && ans <= n; ++i) {
if(a[i] < x) ans += x - a[i];
else ans += min(a[i] % x, x - a[i] % x);
}
if(ans > n) ans = n;
return ans;
}
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]);
int T = 50;
mt19937 rnd(time(0));
while(T--) {
LL x = a[rnd() % n + 1];
div(x - 1), div(x), div(x + 1);
}
sort(vec.begin(), vec.end());
auto it = unique(vec.begin(), vec.end());
vec.erase(it, vec.end());
int ans = n;
for(LL x : vec) ans = min(ans, solve(x));
printf("%d\n",ans);
}