做法大同小异，但不知道为啥我跑这么慢而且还容易被卡。/kk
由于这题看上去和概率一点关系都没有并且 CF 标签中有 probabilities，不难想到随机。
由于答案子集大小至少为 \(n\) 的一半，我们每次随机一个数 \(a_i\)，它在最终答案集合里的概率为 \(\frac{1}{2}\)。然后接下来我们考虑硬点 \(a_i\) 在答案集合里面的最大可能 \(\gcd\)。
注意到此时答案一定为 \(a_i\) 的因数，不超过 \(6720\) 种。所以我们可以直接枚举 \(a_i\) 的因数 \(d\)，然后统计包含这个因数 \(d\) 的 \(a_j\) 的个数，如果个数 \(\ge \frac{n}{2}\) 就更新答案。注意到 \(d\mid a_j,d\mid a_i\Leftrightarrow d\mid \gcd(a_i,a_j)\)，并且 \(\gcd(a_i,a_j)\mid a_i\)，于是只需要对 \(\gcd(a_i,a_j)\) 开 unordered_map 就可以统计出包含某个因数 \(d\) 的 \(a_j\) 的个数，复杂度为 \(O(d^2(a_i))\)。
所以总复杂度为 \(O(T(n\log A+d^2(A)))\)，\(A\) 为值域。取 \(T=20\) 有大概率通过，因为我被卡常了，所以手写哈希替换 unordered_map。
// Problem: Ghd
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF364D
// Memory Limit: 250 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define pb emplace_back
#define mt make_tuple
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
mt19937 rnd(time(0));
const int N = 1e6 + 100;
const int K = 1e7 + 7;
int n, tot, tote, hd[K], c[N];
ll mx, a[N], vl[N], s[N];
struct ed { int to, nxt; ll w; } e[K];
vector<int> pos;
int gt(ll x) {
int p = x % K; pos.pb(p);
for (int i = hd[p]; i; i = e[i].nxt)
if (e[i].w == x) return e[i].to;
vl[++tot] = x, e[++tote] = (ed) { tot, hd[p], x }, hd[p] = tote;
return tot;
}
ll calc(ll x) {
for (int i : pos) hd[i] = 0;
for (int i = 1; i <= tot; i++) c[i] = s[i] = vl[i] = 0;
tot = tote = 0, pos.clear();
for (int i = 1; i <= n; i++) c[gt(__gcd(a[i], x))]++;
for (int i = 1; i <= tot; i++)
for (int j = 1; j <= tot; j++)
if (vl[i] % vl[j] == 0)
s[j] += c[i];
ll res = 0;
for (int i = 1; i <= tot; i++)
if (s[i] >= (n + 1) / 2) res = max(res, vl[i]);
return res;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], mx = max(mx, a[i]);
ll res = 0;
for (int T = ((mx <= 1e7) ? 21 : 12); T; T--)
res = max(res, calc(a[rnd() % n + 1]));
cout << res << '\n';
}
bool Med;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}