CodeForces-1305F Kuroni and the Punishment

传送门：CodeForces-1305F

思路分析

考虑最坏情况，当$gcd$为$2$的时候，最坏$n$次操作就能满足，因此操作上限是$n$
若$gcd$不为$1$，只要每个数都能整除某个质因子$p$,每个数组贪心的统计答案
因为上面得到了操作上限，可以推出，在最优的情况下，至少有一半的数操作最多$1$次
所以在数列里随机找一个数，这个有$\frac{1}{2}$的概率找到最多只操作一次的数
然后将这个数的三种情况进行质因数分解，插入到集合中，最后枚举每个质因子
进行30次抽取，得不到正确答案的概率为$2^{-30}$，概率非常小

样例输入

5
9 8 7 3 1

样例输出

4

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

set<ll>s;
ll a[N];

void init(ll x) {
    for(ll i=2; i*i<=x; i++) {
        if(x%i==0) {
            while(x%i==0)x/=i;
            s.insert(i);
        }
    }
    if(x>1)
        s.insert(x);
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    for(int i=1; i<=30; i++) {
        int x=rng()%n;
        if(a[x]>2)
            init(a[x]-1);
        init(a[x]);
        init(a[x]+1);
    }
    ll ans=n+1;
    for(auto x:s) {
        ll sum=0;
        for(int i=0; i<n; i++) {
            if(a[i]>=x) sum+=min(a[i]%x,x-a[i]%x);
            else sum+=x-a[i];
        }
        ans=min(ans,sum);
    }

    cout<<ans<<endl;






    return 0;
}