Codeforces 1305F. Kuroni and the Punishment

原题链接：https://codeforces.com/contest/1305/problem/F

随机数过题法，记录一下。clock函数和mt19937学到了。

//#pragma GCC optimize(3)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pp;
const int N=2e5+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
mt19937 rnd(time(0));
ll a[N];
ll ans=0x3f3f3f3f3f3f3f3f;
int n;
void solve(ll x)
{
    ll res=0;
    for(int i=0;i<n;i++){
        if(a[i]<x)res+=x-a[i];
        else res+=min(a[i]%x,x-a[i]%x);
    }
    //cout<<x<<" "<<res<<endl;
    ans=min(ans,res);
}
ll p[N],cnt;
void work(ll x)
{
    cnt=0;
    for(ll i=2;i*i<=x;i++){
        if(x%i==0)solve(i);
        while(x%i==0)x/=i;
    }
    if(x!=1)solve(x);
}
int main()
{
    clock_t begin,end;
    begin=clock();
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",a+i);
    }
    solve(2);
    solve(3);
    int k=100;
    while(1){
        ll p=rnd()%n;//cout<<p<<endl;
        work(a[p]+1);
        work(a[p]);
        if(a[p]-1>2)work(a[p]-1);
        end=clock();
        if((end-begin)*1.0/CLOCKS_PER_SEC>2.0)break;
    }printf("%lld
",ans);
    return 0;
}