ABC393E题解

· · 题解

题意

给定一个长度为 n 的序列 a 和一个整数 k，对于每个 i，求出必须选 a_i 的情况下选 k 的数的最大 \gcd。

思路

首先思考原始问题，在长度为 n 的序列中选 k 个数的最大 \gcd。这是有原题的。P1414 又是毕业季II。

做法是：枚举每个数的因子，把它加到桶里。从大到小枚举所有因子，如果某个数出现次数大于等于 k 就是答案。

但这个题不能枚举因子，因为 10^6 的数据随便把 O(n\sqrt n) 的复杂度卡掉。

这个题是这样统计因子的：设 t_i 表示 i 在 a 中出现的次数，m 表示 \max(a_1,a_2,\dots,a_n)，f_x 表示 x 是 a 中 f_x 个数的因子。枚举每个 x，\displaystyle f_x=\sum^{K\times x\le m}_{K=1}t_K。

答案这样统计：设 ans_{i} 表示必须选 i 这个数的答案。从大到小枚举每个数 x，如果它作为因子的次数大于 k，那么 x,x\times2,x\times3,\dots 的答案就都是 x。

最后的答案，输出 ans_{a_i} 即可。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,k,a[1200005],t[N],f[N],ans[N],m;
signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>a[i],t[a[i]]++,m=max(m,a[i]);
    for(int i=1; i<=m; i++) for(int j=i; j<=m; j+=i) f[i]+=t[j];
    for(int i=m; i>=1; i--)
        if(f[i]>=k)
            for(int j=i; j<=m; j+=i)
                if(!ans[j]) ans[j]=i;
    for(int i=1; i<=n; i++) cout<<ans[a[i]]<<'\n';
    return 0;
}