Codeforces #213 Div1 D. Ghd

これは思いつかんなぁ。
http://codeforces.com/contest/364/problem/D

問題

N要素の整数列Aが与えられる。
数列のGHDとは、数列の半分以上の要素の公約数であるような数の最大値である。

AのGHDを求めよ。

解法

GHDは過半数の要素の約数である。
よって、ランダムで要素を選ぶと、半分以上の確率でGHDの倍数になっている。

そこで乱択で解くことを考えよう。
ランダムにAの要素1つA[r]を選ぶ。
あとはGCD(A[i],A[r])の約数のうち過半数となる最大値を求める。

半分以上の確率で上記値は解になるので、10回もやれば99%以上の確率で正解する。

int N;
ll A[1010000];
ll ma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	srand(time(NULL)+A[0]);
	FOR(i,10) {
		j=(rand()*1007LL+rand()+rand()*13LL)%N;
		vector<ll> V;
		FOR(k,N) V.push_back(__gcd(A[j],A[k]));
		vector<pair<ll,int> > V2;
		sort(ALL(V));
		FOR(k,N) {
			if(V2.empty() || V2.back().first!=V[k]) V2.push_back(make_pair(V[k],1));
			else V2.back().second++;
		}
		
		ITR(it,V2) if(ma<it->first) {
			x=0;
			for(vector<pair<ll,int> >::iterator it2=it;it2!=V2.end()&&x<(N+1)/2;it2++)
				if(it2->first%it->first==0) x+=it2->second;
			if(x>=(N+1)/2) ma=it->first;
		}
	}
	cout<<ma<<endl;
	
}

まとめ

これ解いてるの1年以上前だ。
早く書かないと忘れそうだ。