- 赛时想了 1.5h 没想出来做法，然后写了个随机化乱搞过了，有点侥幸。
思路
赛时想到：
- 答案上界为 \(n\)。
需要进阶：
-
变化超过 \(1\) 的数的个数 \(\le \lfloor\frac{n}{2}\rfloor\)。
-
所以随机一个数，这个数变化不超过 \(1\) 的概率 \(\ge\frac{1}{2}\)。
-
于是每次随机一个数，验证一下 \(a_i-1,a_i,a_i+1\) 的所有质因子即可。
-
随机个 \(30\) 次即可保证 \(1-10^{-9}\) 的正确率。
需要考虑到一次质因数分解就需要跑 \(8e4\) 次，所以能够接受的分解次数较少，尽量少分解，多验证。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10,M=1e6+10,V=1e6;
const ll INF=1e18;
int n;
ll a[N];
void read(ll &x){
char c;
for(x=0;!isdigit(c=getchar()););
for(;x=(x<<3)+(x<<1)+(c^48),isdigit(c=getchar()););
}
int cnt,vis[M],pri[M];
void init(){
for(int i=2;i<=V;i++){
if(!vis[i])pri[++cnt]=i;
for(int j=1;j<=cnt&&i*pri[j]<=V;j++){
vis[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
mt19937 rnd(time(0));
ll ans=INF;
set<ll>s;
void calc(ll p){
if(s.count(p))return;
s.insert(p);
ll sum=0;
for(int i=1;i<=n&&sum<ans;i++){
if(a[i]<p)sum+=p-a[i];
else sum+=min(a[i]%p,p-a[i]%p);
}
ans=min(ans,sum);
}
void divide(ll x){
for(int i=1;i<=cnt&&1ll*pri[i]*pri[i]<=x;i++){
if(x%pri[i])continue;
calc(pri[i]);
for(;x%pri[i]==0;x/=pri[i]);
}
if(x>1)calc(x);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)read(a[i]);
init();
for(int i;;){
i=rnd()%n+1;
if(a[i]>1)divide(a[i]-1);
divide(a[i]),divide(a[i]+1);
if(1.0*clock()/CLOCKS_PER_SEC>0.85)break;
}
cout<<ans;
return 0;
}