3152数值选取挑战

在本挑战中，您将面对一系列正整数（总数为n，其中2 <= n <= 100000）。您的任务是从这组数字中选择大约一半数量的数字，即向上取整后的n/2个数，以确保这些被选中的数字的最大公约数（GCD）达到最大值。请计算并返回这个最大可能的GCD值。

输入的第一行包含一个整数n，代表数字的数量。
第二行则包含了n个正整数。

输出一行，仅包含一个整数，即所求的最大GCD值。

对于10%的数据，2 <= n <= 10。
对于30%的数据，2 <= n <= 300。
对于60%的数据，2 <= n <= 5000。
对于100%的数据，2 <= n <= 100000。

输入示例1:
6
6 2 3 4 5 6
输出示例1:
3

输入示例2:
5
5 5 6 10 15
输出示例2:
5

以下是解决此问题的一种方法的C++实现代码：

#include
#include
#include
#include
#include
#define maxn 1000000
#define maxt 10
using namespace std;
typedef long long ll;
int n;
ll a[maxn+5];
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
int random(int l, int r) {
    return (long long)rand() * rand() % (r - l + 1) + l;
}
int sz = 0;
ll d[maxn+5];
int cnt[maxn+5];
void divide(ll x) {
    sz = 0;
    for (ll i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d[++sz] = i;
            if (x / i != i) d[++sz] = x / i;
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
    ll ans = 0;
    for (int cas = 1; cas <= maxt; cas++) {
        ll x = a[random(1, n)];
        divide(x);
        sort(d + 1, d + sz + 1);
        for (int i = 1; i <= sz; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) {
            int pos = lower_bound(d + 1, d + 1 + sz, gcd(a[i], x)) - d;
            cnt[pos]++;
        }
        for (int i = 1; i <= sz; i++) {
            for (int j = i + 1; j <= sz; j++) {
                if (d[j] % d[i] == 0) cnt[i] += cnt[j];
            }
        }
        for (int i = sz; i >= 1; i--) {
            if (cnt[i] * 2 >= n) {
                ans = max(ans, d[i]);
                break;
            }
        }
    }
    printf("%I64d\n", ans);
    return 0;
}