[CF364D]Ghd

题目大意：

有\(n(n\le10^6)\)个数\(A_{1\sim n}(A_i\le10^{12})\)，从中选取\(\lceil\frac n2\rceil\)个数，使得这些数的\(\gcd\)最大，求最大\(\gcd\)。

思路：

每个数有超过\(\frac12\)的概率被选取，因此可以随机一个数\(A_k\)，强制要求它在被选取的集合内。对于所有\(A_i\)，求\(\gcd(A_i,A_k)\)，令\(B_i=\gcd(A_i,A_k)\)。从大到到小枚举每一个\(B_i\)，统计有多少\(B_j\)是其倍数，若超过\(\lceil\frac n2\rceil\)则说明是一种可能的解，更新\(ans\)。

多随机几次正确率大大提高，然后剪剪枝就过了。

源代码：

#include<map>

#include<ctime>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<algorithm>

typedef long long int64;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e6+1;

int64 a[N];

std::map<int64,int> map;

int main() {

	srand(time(NULL));

	const int n=getint();

	for(register int i=1;i<=n;i++) {

		a[i]=getint();

	}

	int64 ans=0;

	for(register int T=0;T<10;T++) {

		const int k=1ll*rand()*rand()%n+1;

		if(a[k]<=ans) continue;

		map.clear();

		for(register int i=1;i<=n;i++) {

			if(a[i]<=ans) continue;

			const int64 x=std::__gcd(a[i],a[k]);

			if(x>ans) map[x]++;

		}

		std::vector<std::pair<int64,int>> v(map.begin(),map.end());

		std::reverse(v.begin(),v.end());

		for(register unsigned i=0;i<v.size();i++) {

			if(v[i].first<ans) break;

			int cnt=0;

			for(register unsigned j=0;j<=i;j++) {

				if(v[j].first%v[i].first==0) {

					cnt+=v[j].second;

				}

				if(cnt>=(n+1)/2) break;

			}

			if(cnt>=(n+1)/2) ans=v[i].first;

		}

	}

	printf("%I64d\n",ans);

	return 0;

}