CF364D Ghd

John Doe 提议他的妹妹 Jane Doe 求一组数 $a$ 的最大公约数（gcd）。 最大公约数指的是一个正整数 $g$，使得集合中的所有数都能被 $g$ 整除，并且不存在大于 $g$ 的正整数 $g'$，使得所有数都能被 $g'$ 整除。 不幸的是，Jane 没能完成这个任务，于是 John 又建议她求同一组数的最大半公约数（ghd）。 最大半公约数（ghd）是指一个正整数 $g$，使得集合中至少一半的数都能被 $g$ 整除，并且不存在大于 $g$ 的正整数 $g'$，使得集合中至少一半的数都能被 $g'$ 整除。 Jane 花了两个小时才完成这个任务。请你也尝试一下。

第一行包含一个整数 $n$（$1 \le n \le 10^{6}$），表示集合 $a$ 中有多少个数。 第二行包含用空格分隔的 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{12}$）。集合中可能包含相等的数。 请注意，在 C++ 中读写 64 位整数时请不要使用 %lld 格式符，建议使用 %I64d。

输出一个正整数 $g$，即集合 $a$ 的最大半公约数（ghd）。

由 ChatGPT 5 翻译