Codeforces 364D 随机算法

题意：给你一个序列，定义ghd为一个序列中任意n / 2个数的gcd中最大的那个，现在问这个序列的ghd为多少。

思路：居然是论文题。。。来自2014年国家集训队论文《随机化算法在信息学竞赛中的应用》，作者胡泽聪。

这里大概记录一下思想：先不考虑复杂度，考虑枚举。对于每个枚举的数，我们假设它在构成ghd的集合中，那么怎么求ghd呢？首先，如果选择的数（x）在ghd集合中，那么ghd一定是x的因子。我们可以先让x和其它的数求gcd，然后如果gcd的某个因子也是x的因子，那么对应因子的数目++。实际实现不需要对每个gcd因式分解，如果gcd本身就是x的因子，在对应项+1.之后，我们从小到大枚举因子，把比它大的并且能被自己整除因子的贡献加到自己身上就可以了。假设因子个数是g(x), 那么单次枚举的复杂度是O(nlogn + g(x) ^ 2 + x ^ (1 / 2))。我们考虑随机，因为每次选x都有一半的概率选到最大的ghd的集合中，所以我们选12个点，取最大值就可以了，错误概率为1 - ((1 / 2) ^ 12))，已经很小了。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1000010;
LL ans = 0;
mt19937 random(time(0));
vector<LL> fac;
LL a[maxn], g[maxn];
int n;
void div(LL n) {
	fac.clear();
	for (LL i = 1; i * i <= n; i++) {
		if(n % i == 0) {
			fac.push_back(i);
			if(i * i != n) fac.push_back(n / i);
		}
	}
	sort(fac.begin(), fac.end());
}
void solve(int p) {
	for (int i = 1; i <= n; i++)
		g[i] = __gcd(a[i], a[p]);
	div(a[p]);
	vector<LL> sum(fac.size());
	for (int i = 1; i <= n; i++) {
		int pos = lower_bound(fac.begin(), fac.end(), g[i]) - fac.begin();
		if(pos >= 0 && pos < fac.size()) sum[pos]++;
	}
	for (int i = 0; i < fac.size(); i++) {
		for (int j = i + 1; j < fac.size(); j++) {
			if(fac[j] % fac[i] == 0) sum[i] += sum[j];
		}
	}
	for (int i = fac.size() - 1; i >= 0; i--) {
		if(sum[i] * 2 >= n) {
			ans = max(ans, fac[i]);
			return; 
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= 12; i++) {
		int pos = random() % n + 1;
		solve(pos);
	}
	printf("%lld
", ans);
}