← 返回题目列表

Codeforces · 364/D

D. 最大公约数

中文机器翻译题面 查看原题

John Doe 向他的妹妹 Jane Doe 提出求某组数字 a 的 gcd。

Gcd 是一个正整数 g,使得集合中的所有数字都可以被 g 整除,并且不存在这样的 g' (g' > g),即集合中的所有数字都可以被 g' 整除。

不幸的是,简无法完成这项任务,约翰让她找到同一数字子集的 ghd。

Ghd 是一个正整数 g,使得该集合中的至少一半的数字可以被 g 整除,并且不存在这样的 g' (g' > g) 使得该集合中的至少一半的数字可以被 g' 整除。

Jane 花了两个小时完成这项任务。请你也尝试一下。

输入

第一行包含一个整数 n (1 ≤ n ≤ 106),显示集合 a 中有多少个数字。第二行包含空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 1012)。请注意,给定的集合可以包含相同的数字。

请不要使用 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 %I64d 说明符。

输出

打印单个整数 g — 集合 a 的 Ghd。

示例

输入 #1

6
6 2 3 4 5 6

输出 #1

3

输入 #2

5
5 5 6 10 15

输出 #2

5