http://codeforces.me/contest/364/problem/D description: a set A of positive integers, if all integers in A are divisible by g, (the max of g), g is called gcd of the set A. Then, if just at least half integers in A are divisible by g, (the max of g), g is called ghd of the set A. problem: give the set A, find its ghd.

since the set size if hugh n=10^6, and the integers in set A is huge too, ai=10^12, we could only use some algorithm with O(n) or O(nlogn) time.

there is one solution, let's say an integer set fac(x):any integer in fac(x) could divide x. fac(x) is a divisor set of integer x. First we find all fac(ai), and if there exist ghd, ghd is the element of fac(ai), at least half ai. Then, we just count the appearance times of all the divisor of all ai, if some divisor appearance at least (n+1)/2 times, then this divisor could be ghd. However, the size of fac(ai) is about 10^3, which O( 10^6 * 10^3 ) is TLE.

The following in this blog is the thought of a big guy, although I did not know who is the real author, I just want to share his idea of this problem.

Solution: we randomly get some integers in set A, for each ai, we calculate fac(ai), O(sqrt(ai)) times, and we just check the possible element in fac(ai) that could be the ghd, that is, for each divisor in fac(ai), check if it could divide at least half integers in set A. For one ai we choose, check all its divisor, and we select about 10 ai to check, then print the max ghd we find.

Why is it right? we just randomly check 10 integers in set A. Yes, it is right!

if we just miss the real max ghd, then this real max ghd must exist in at least half of fac(ai). so each time we randomly choose the ai to check, we has a possibility of 0.5 to miss it. And if for 10 times, we just all miss it, the possibility is 1/2^10, how small it is, we could hardly miss it.

This is the magic!