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
*/
标签:10,cnt,ch,int,题解,因数,Ghd,CF364D,枚举
From: https://www.cnblogs.com/Meteor-streaking/p/17734246.html