专栏文章

ABC393E题解

LLovely_yhb
AT_abc393_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq8snj2
此快照首次捕获于
2025/12/04 00:49
3 个月前
此快照最后确认于
2025/12/04 00:49
3 个月前
查看原文

题意

给定一个长度为 nn 的序列 aa 和一个整数 kk，对于每个 ii，求出必须选 aia_i 的情况下选 kk 的数的最大 gcd⁡\gcd。

思路

首先思考原始问题，在长度为 nn 的序列中选 kk 个数的最大 gcd⁡\gcd。这是有原题的。P1414 又是毕业季II。
做法是：枚举每个数的因子，把它加到桶里。从大到小枚举所有因子，如果某个数出现次数大于等于 kk 就是答案。
但这个题不能枚举因子，因为 10610^6 的数据随便把 O(nn)O(n\sqrt n) 的复杂度卡掉。
这个题是这样统计因子的：设 tit_i 表示 ii 在 aa 中出现的次数，mm 表示 max⁡(a1,a2,…,an)\max(a_1,a_2,\dots,a_n)，fxf_x 表示 xx 是 aa 中 fxf_x 个数的因子。枚举每个 xx，fx=∑K=1K×x≤mtK\displaystyle f_x=\sum^{K\times x\le m}_{K=1}t_K。
答案这样统计：设 ansians_{i} 表示必须选 ii 这个数的答案。从大到小枚举每个数 xx，如果它作为因子的次数大于 kk，那么 x,x×2,x×3,…x,x\times2,x\times3,\dots 的答案就都是 xx。
最后的答案，输出 ansaians_{a_i} 即可。

AC Code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...