「CF364D」Ghd

2015年1月20日3,8240

John Doe offered his sister Jane Doe find the gcd of some set of numbers a.

Gcd is a positive integer g, such that all number from the set are evenly divisible by g and there isn’t such g (g‘ > g), that all numbers of the set are evenly divisible by g.

Unfortunately Jane couldn’t cope with the task and John offered her to find the ghd of the same subset of numbers.

Ghd is a positive integer g, such that at least half of numbers from the set are evenly divisible by g and there isn’t such g (g‘ > g) that at least half of the numbers from the set are evenly divisible by g.

Jane coped with the task for two hours. Please try it, too.

Input

The first line contains an integer n (1 ≤ n ≤ 106) showing how many numbers are in set a. The second line contains space-separated integers a1, a2, …, an (1 ≤ ai ≤ 1012). Please note, that given set can contain equalnumbers.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the %I64dspecifier.

Output

Print a single integer g — the Ghd of set a.

Sample test(s)
input

output

input

output

搬运hgg的题解

考虑枚举一个存在于最终答案的集合内的数x,这样子,可行的gcd的范围就变成了x的因子个数,在10^12以内,最多的因子个数只有6000多个。

对于其他元素,我们关注的只有它们和当前枚举的数x的gcd了。所以可以O(nlogC)地求出来。同时,我们可以记录cnt[i]表示和x的gcd为i的有多少个。显然只有6000级别个的cnt不会为0,我们可以非常轻松地记录下来。

现在我们直接枚举一下最终的答案是多少,只需要统计有多少个数含有这个因子即可。明显复杂度可以做到6000^2。

所以假如我们枚举了一个x,现在的复杂度是O(sqrt10^12+nlogC+6000^2),看起来还是可以接受的。 假如我们随机到的位置存在于最优解中,那么我们一定能够得出最优解。 注意到我们随机一个位置有1/2的概率存在于最优解中。 多随机几次即可。

 

 

avatar
  Subscribe  
提醒