【Ozon Tech Challenge 2020 F】Kuroni and the Punishment 题解

题目大意

  有一个正整数序列 $a_1,\cdots,a_n$，每次操作可以把一个数 $+1$ 或 $-1$，但要使其仍为正数。问至少多少次操作，使得整个序列的 $\gcd$ 不为 $1$。
  $n \le 2 \times 10^5$
  2.5s

题解

  首先有些很明显的观察，比如，可以枚举一个 $a_i$ 的质因数 $p$ 作为 $\gcd$，然后每个数变成 $\min(a_i \bmod p,p-a_i \bmod p)$，这样判一次是 $O(n)$ 的。
  再比如，答案不会超过序列中奇数的数量，因为每个奇数 $+1$ 就会使得 $2|\gcd$。
  然后。。。
  就没有然后了。。。

  然后题解说，虽然判一个质因子要 $O(n)$，但是只用判很少的质因子。
  由观察 2，答案不超过 $n$，因此最终改动在 $1$ 以内的位置至少有 $\frac n2$ 个。也就是说，任选一个位置，至少有 $\frac n2$ 的概率，最终的 $\gcd$ 被它的质因子整除。
  因此就随机选序列的 20 个数，判断 $a_i,a_i+1,a_i-1$ 的所有质因子，就行了~

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=2e5+5;

int n;
LL a[maxn];

LL _check(LL p)
{
	LL ans=0;
	fo(i,1,n) ans+=(a[i]<p) ?p-a[i] :min(a[i]%p,p-a[i]%p);
	return ans;
}
LL check(LL x)
{
	LL ans=n+500;
	int sqrtx=sqrt(x);
	for(int i=2; i<=sqrtx; i++) if (x%i==0)
	{
		ans=min(ans,_check(i));
		while (x%i==0) x/=i;
	}
	if (x>1) ans=min(ans,_check(x));
	return ans;
}

int main()
{
	scanf("%d",&n);
	fo(i,1,n) scanf("%lld",&a[i]);
	
	LL ans=0;
	fo(i,1,n) ans+=(a[i]&1);
	
	random_shuffle(a+1,a+1+n);
	random_shuffle(a+1,a+1+n);
	random_shuffle(a+1,a+1+n);
	fo(i,1,min(n,20))
	{
		ans=min(ans,check(a[i]-1));
		ans=min(ans,check(a[i]));
		ans=min(ans,check(a[i]+1));
	}
	
	printf("%lld\n",ans);
}