Solution CF1305F Kuroni and the Punishment

题意简述：

给定长度为 n 的数组 a_i。每次你可以花费 1 的代价使 a_i 加上或者减去 1。要求最小化代价使得所有 a_i 都是质数 k 的倍数。n \leq 10^5,\ a_i \leq 10^{12}。

思路分析：

首先我们令 k = 2，得到 ans \leq n。也就是说，对于最优解的画面，至多有 \lfloor \frac n 2 \rfloor 个整数的变化幅度超过 1。

设定阀值 \omega，我们随机从 a_{1 \dots n} 中选择 k 个数 x_{1 \dots k}，每次检查 x-1,x,x+1 的每个质因子是否为答案。复杂度为 O(n \sigma (a) \times \omega)，正确率为 1 – (\frac 1 2)^{\omega}。

细节分析：

1. 可以用通过 clock() 函数控制循环次数。本题时限2.50s，实测 time_limit 设为 0.10s 可通过本题。

2. 由于洛谷对于CF题目采用RemoteJudge方式评测，即将代码发回CF测评，考虑到CF采用windows环境评测，rand() 函数的取值范围在 [0, 32767]，考虑使用 std::mt19937 替代。

模板代码：

std::mt19937 rng(20040725^std::chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline T rand(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}

完整代码：

#include<bits/stdc++.h>
template<class T> inline void read(T &x){
  x=0; register char c=getchar(); register bool f=0;
  while(!isdigit(c))f^=c=='-',c=getchar();
  while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
std::mt19937 rng(20040725^std::chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline T rand(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
const int N=2e5+10;
int n;
long long a[N];
std::set<long long> checked,calced;
long long check(long long x){
  if(checked.count(x))return LLONG_MAX;
  checked.insert(x);
  long long ans=0;
  for(int i=1;i<=n;i++)if(a[i]<=x){
    ans+=x-a[i];
  }else{
    ans+=std::min(a[i]%x,x-a[i]%x);
  }
  return ans;
}
long long calc(long long x){
  if(!x||calced.count(x))return LLONG_MAX;
  calced.insert(x);
  long long ans=LLONG_MAX;
  // printf("check %lld => ",x);
  for(long long i=2;i*i<=x;i++)if(x%i==0){
    ans=std::min(ans,check(i));
    while(x%i==0)x/=i;
  }
  if(x!=1)ans=std::min(ans,check(x));
  // printf("œ%lld\n",ans);
  return ans;
}
int main(){
#ifdef CF1305F
  freopen("data.in","r",stdin);
#endif
  read(n),srand(20040725);
  for(int i=1;i<=n;i++)read(a[i]);
  for(int i=n;i>=1;i--)std::swap(a[i],a[rand(1,i)]);
  long long ans=LLONG_MAX;
  for(int k=1;k<=n&&clock()/(double)CLOCKS_PER_SEC<.1;k++){
    ans=std::min(ans,calc(a[k]));
    ans=std::min(ans,calc(a[k]+1));
    ans=std::min(ans,calc(a[k]-1));
  }
  printf("%lld\n",ans);
}