CF1305F Kuroni and the Punishment 题解

这个在看到标签有随机化后确实是一眼吧。

首先答案肯定有一个上街就是奇数个数 $\leq n$。这也就意味着至少有 $\leq n\over 2$ 个数只被操作了 $\leq 2$ 次。于是我们随机选一个数他被操作了 1 或 0 次的概率就是 $1\over 2$。设我们随机 $B$ 个数找他们的质因数。那么错误概率就是 $1\over 2^B$。

// Problem: Kuroni and the Punishment
// URL: https://www.luogu.com.cn/problem/CF1305F
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e5 + 10;
int a[MAX];
std::mt19937 Rnd(114514);

map <int, int> mp;
vector <int> b;

void solve(){
	int n = read();
	int ans = 0;
	for(int i = 1; i <= n; i++){
		a[i] = read();
		ans += a[i] % 2;
		// if(a[i] != 1 and n > 10)	{
			// write(a[i]), put();
			// endl;
		// }
	}
	int now = a[1];
	for(int i = 2; i <= n; i++){
		now = __gcd(now, a[i]);
	}
	if(now != 1){
		puts("0");
		return ;
	}
	int t = 40;
	while(t--){
		int x2 = Rnd() % n + 1;
		// write(x2), endl;
		for(int k = a[x2] - 1; k <= a[x2] + 1; k++){
			int x = k;
			for(int i = 2; i * i <= x; i++){
				if(x % i)	continue;
				while(x % i == 0)	x /= i;
				if(mp.count(i))	continue;
				mp[i] = 1;
				b.pb(i);
			}
			if(x >= 2){
				if(mp.count(x))	continue;
				mp[x] = 1;
				b.pb(x);
			}
		}
	}
	for(int u : b){
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			if(a[i] <= u){
				cnt += u - a[i];
			}else{
				cnt += min(a[i] % u, u - (a[i] % u));
			}
		}
		// write(1);
		ans = min(ans, cnt);
	}
	write(ans), endl;
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}