你考虑一件事，就是说改变次数 $\geq \lfloor \frac{n}{2} \rfloor$ 的数最多有 $\lfloor \frac{n}{2} \rfloor$ 个，证明较为简单。

所以我们得到了一个算法：你直接在数列里随50个数，然后把它、它 $+1$、它 $-1$ 这三个数分解质因数扔到一个set里。对于每一个set的里元素，暴力求解即可。

你考虑正确率。每次随机一个元素，它被操作了的概率是 $\frac 1 2$，所以你随机 $50$ 次的正确率是：$\frac{1}{2^{50}}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll p[1000005],v[1000005],n,m,a[1000006],mx=10,cnt,k,ans=1e9;
mt19937 rd((unsigned long long)new char);
set<long long>g;
void insert(ll x){
    for(long long i=1;i<=cnt&&p[i]*p[i]<=x;++i){
        if(x%p[i]==0){
            g.insert(p[i]);
            while(x%p[i]==0)x/=p[i];
        }
    }
    if(x>1)g.insert(x);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(long long i=1;i<=n;++i)cin>>a[i],mx=max(mx,a[i]);
    v[1]=1;k=sqrt(mx)+1;
    for(long long i=2;i<=k;++i){
        if(!v[i]){
            p[++cnt]=i;
            for(long long j=i*2;j<=k;j+=i)v[i]=1;
        }
    }
    shuffle(a+1,a+n+1,rd);
    for(long long i=1;i<=min(50ll,n);++i){
        if(a[i]>1)insert(a[i]-1);
        insert(a[i]);insert(a[i]+1);
    }
    for(auto t:g){
        ll sum=0;
        for(long long i=1;i<=n;++i){
            ll x=a[i]/t,l=x*t,r=(x+1)*t;
            if(!l)sum+=r-a[i];
            else sum+=min(r-a[i],a[i]-l);
            if(sum>=ans)break;
        }
        ans=min(ans,sum);
    }
    cout<<ans<<'\n';
    return 0;
}