CF364D Ghd 题解

题目大意

给定一个长度为 \(n\) 的序列，你需要从中选出一个元素个数不少于 \(\left\lceil{\frac{n}{2}}\right\rceil\) 的子序列，使得这个子序列中所有元素的 \(\gcd\) 最大。

分析

数据范围吓人。

\(10^6\)，但是根本想不到什么 \(O(n \log n)\) 或 \(O(n)\) 的算法。然后就开始想其他技巧。

刚开始想的是什么 \(\gcd\) 的性质，但是显然没有什么结果（我赛时就想到这里，然后寄了）。

注意到子序列元素个数比较大，可能比较容易从这入手，所以我们进一步从 \(\left\lceil{\frac{n}{2}}\right\rceil\) 这里分析。

题解

既然我们选至少一半，那么就意味着每一个数都有 \(\frac{1}{2}\) 的几率被选进最终答案的子集。我们可以考虑随机枚举几个数，假设我们枚举了 \(m\) 个数，那么至少有一个数在答案的子集里的概率为 \(1 - \frac{1}{2^m}\)。这个概率其实蛮大的。

然后我们去想对于每一个枚举的数，我们怎么算可能的答案。

如果这个数在最终的子集里，那么意味着最终的 \(\gcd\) 一定是这个数的一个因数。所以我们考虑枚举这个数的所有因数，然后算每个因数在原序列中的出现位置，最后从大到小找到第一个出现次数大于等于 \(\left\lceil{\frac{n}{2}}\right\rceil\) 的数，并与我们最终的 \(ans\) 取 \(\max\)。

实现方面的话，记 \(cnt_i\) 表示第 \(i\) 个因数在原序列中出现的次数。我们先对所有因数排序，然后从 \(1\) 到 \(n\) 枚举原序列的数，与我们当前随机出来的数求 \(\gcd\)，求出来以后在存因数的那个数组里 \(\operatorname{lower\_bound}\) 找（二分也行），使其 \(cnt + 1\)。但是这样明显是不对的，因为如果两个数的 \(\gcd\) 为 \(3\)，那么不仅 \(3\) 的出现次数加一，\(6, 9\) 这一类数的出现次数也会多一次。所以我们最后求完 \(cnt\) 后再枚举一遍因数那个数组，然后对于每个因数 \(i\)，再去枚举一遍小于它的因数 \(j\)，如果 \(i \bmod j = 0\)，那么令 \(cnt_i\) 加上 \(cnt_j\)，这才是最终的 \(cnt\)。

总时间复杂度 \(O(n \log d + d^2)\) 差不多。\(d\) 代表因数个数，其实蛮小的，对于 \(10^{12}\) 以内的数，最多的因数个数也才 \(6720\)。\(m\) 就是我代码里的 \(T\)，我取的 \(10\)，一发 AC 了，\(3.5s\)，没什么问题。

代码

如果你能看懂我用的随机化更好，看不懂就用普通的 \(rand()\) 函数就行。

#include <bits/stdc++.h>
#define int long long
#define M 1000005
#define mod 1000000007
#define time() chrono::system_clock::now().time_since_epoch().count()

using namespace std;

inline int read() {
    int x = 0, s = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')
            s = -s;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * s;
}

void write(int x) {
    if(x < 0)  {
        x = ~(x - 1);
        putchar('-');
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + 48);
}

int n, a[M], ans, d[M >> 2], cnt[M >> 2];

signed main() {
    n = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    int T = 10;
	default_random_engine e;
	uniform_int_distribution<int> Z(1, n);
	srand(time());
	e.seed(rand());
    for(int t = 1; t <= T; ++ t) {
        int r = Z(e);
        int len = 0;
        int x = a[r];
        int sq = sqrt(x);
        for(int i = 1; i <= sq; ++ i)
            if(x % i == 0)
                d[++ len] = i, cnt[len] = 0, d[++ len] = x / i, cnt[len] = 0;
        if(sq * sq == x)
            -- len;
        stable_sort(d + 1, d + 1 + len);
        for(int i = 1; i <= n; ++ i)
            ++ cnt[lower_bound(d + 1, d + 1 + len, __gcd(x, a[i])) - d];
        for(int i = 1; i <= len; ++ i)
            for(int j = i + 1; j <= len; ++ j)
                if(d[j] % d[i] == 0)
                    cnt[i] += cnt[j];
        for(int i = len; i >= 1; -- i) {
            if(cnt[i] * 2 >= n) {
                ans = max(ans, d[i]);
                break;
            }
        }
    }
    write(ans);
}

/*
10
1 2 3 4 5 6 7 8 9 10
*/