Ghd
题意翻译
定义一个集合的Ghd为 所有大小至少为一半的子集的$\mathrm{gcd}$ 的最大值。
给定集合$a$,求$a$的Ghd。
题目描述
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.
输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1<=n<=10^{6} $ ) showing how many numbers are in set $ a $ . The second line contains space-separated integers $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{12}) $ . Please note, that given set can contain equal numbers.
Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the %I64d specifier.
输出格式
Print a single integer $ g $ — the Ghd of set $ a $ .
输入输出样例
输入样例 #1
6
6 2 3 4 5 6
输出样例 #1
3
输入样例 #2
5
5 5 6 10 15
输出样例 #2
5