题目地址：Codeforces：Problem – 364D – Codeforces、洛谷：【CF364D】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 a1, a2, …, an (1 ≤ ai ≤ 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

题解

参考资料：CFR 364 D. Ghd ( Random, Math ) – 0w1
随机化的题目，直接求显然不好办，n的数据范围看着就吓人，直观感觉像O(n \log n)。
我们知道这个数字一定是这个数列中某个数的因数，因此我们需要选择一个数求它与其他数的最大公因数。这些公因数中的一个就是答案。求一遍公因数是O(n \log n)的。
对于求出来的公因数，我们去从大到小找一个会成为超过一半数的因数的数字。具体做法是，选择一个因数，去找比它大的因数，如果它能整除大因数，说明大因数对应的数字也可以被这个数整除，应当把加到这个数的计数上。这个过程直观看上去是O(n^2)的，但是实际上我们不会对比当前最优解还小的因数计算，并且当计数超过n的一半的时候就可以停止计数并计入答案，在这样的处理下我们可以让这个计数的时间变得可接受。
答案肯定是这些数字中超过一半数的因数，因此每一次随机找到正确解的概率超过0.5。我们考虑重复找解的过程多次，这里我使用10次（超过10次似乎会TLE 18）。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <ctime>
#include <cstdlib>

#include <map>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005;

inline LL gcd(LL a, LL b) {
    LL t;
    while(b) {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int n;
LL a[MAXN];

int main() {
    srand(time(NULL));
    n = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    LL ans = 1;
    for(int rep = 1; rep <= 10; rep++) { // bad rand
        int rnd = (rand() * RAND_MAX + rand()) % n + 1;
        std::map<LL, int> fact;
        for(int i = 1; i <= n; i++) {
            LL t = gcd(a[i], a[rnd]);
            if(!fact.count(t)) fact[t] = 1;
            else fact[t]++;
        }
        std::map<LL, int>::iterator it = fact.end();
        do {
            it--;
            if((*it).first <= ans) continue;
            int cnt = 0;
            for(std::map<LL, int>::iterator it1 = it; 
                it1 != fact.end() && cnt << 1 < n; it1++) {
                if(!((*it1).first % (*it).first)) {
                    cnt += (*it1).second;
                }
            }
            if(cnt << 1 >= n) ans = (*it).first;
        } while(it != fact.begin());
    }
    printf("%I64d", ans);
    return 0;
}