首先注意到每个数最多操作1次就能让他变成2的倍数，所以答案\(\le n\)。如果我们能枚举[1,1e12]中所有的质数，并对每个质数p求出把数组中所有数都变成它的倍数的最少步数\(c_p\)，那就能求出答案了。但是质数太多了不能一个个枚举。令\(c_p\)最小的质数为P，如果有多个最小的则任取一个。显然在\(a_1,a_2\cdots a_n\)中，有至少一半能够用0或1步变成P的倍数，也就是\(P|a_i或P|a_i-1或P|a_i+1\)。如果我们随机选一个位置i，并对\(a_i,a_i-1,a_i+1\)的所有质因数x求出\(c_x\)并更新答案，有\(\frac 12\)的概率查到P并得到最优解。所以随机个几十次找不到最优解的概率就很小了。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define pdd pair <double,double>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
mt19937 rnd(114514);
LL n,a[200010],ans=1e18;
void checkP(LL val)
{
LL ret=0;
rep(i,n)
{
LL dv=a[i]%val,res=min(dv,val-dv);
if(a[i]<val) res=val-a[i];
ret+=res;
}
ans=min(ans,ret);
}
void check(LL val)
{
for(LL i=2;i*i<=val;++i) if(val%i==0)
{
while(val%i==0) val/=i;
checkP(i);
}
if(val>1) checkP(val);
}
int main()
{
fileio();
cin>>n;
rep(i,n) scanf("%lld",&a[i]);
rep(ti,50)
{
LL i=rnd()%n;
check(a[i]);check(a[i]+1);
if(a[i]>1) check(a[i]-1);
}
cout<<ans<<endl;
termin();
}