专栏文章

题解：CF2039D Shohag Loves GCD

MMeickol
CF2039D题解参与者 1已保存评论 0

文章操作

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

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

数论 + 贪心构造

设最终的答案数组为 bb。
手玩一下数据：
当 i=1i=1 时，显然对于任意的 j (j>i)j \ (j \gt i) 都满足 gcd⁡(i,j)=1\gcd(i,j)=1，那么要保证 b1≠gcd⁡(b1,bj)b_1 \ne \gcd(b_1,b_j)，即保证 ∀j∈[2,n],b1∤bj\forall j \in [2,n] , b_1 \nmid b_j。根据贪心策略不难想到让 b1b_1 取序列 aa 中的最大值。
当 i=2i=2 时，显然对于所有的 j (j>i∧i∣j)j \ (j \gt i \wedge i \mid j) 满足 gcd⁡(2,j)=2\gcd(2,j)=2，那么要保证 b2≠gcd⁡(b2,bj)b_2 \ne \gcd(b_2,b_j)，即保证 ∀j (j∈[4,n]∧i∣j),b2∤bj\forall j \ (j\in [4,n] \wedge i \mid j) , b_2 \nmid b_j。根据贪心策略将 b2b_2 设置为序列 aa 中次大值。
当 i=3i=3 时，同样地，显然对于所有的 j (j>i∧i∣j)j \ (j \gt i \wedge i \mid j) 满足 gcd⁡(3,j)=3\gcd(3,j)=3，那么要保证 b3≠gcd⁡(b3,bj)b_3 \ne \gcd(b_3,b_j)，即保证 ∀j (j∈[6,n]∧i∣j),b3∤bj\forall j \ (j\in [6,n] \wedge i \mid j) , b_3 \nmid b_j。同时，由于 33 是质数，对于任意的 k (k<i)k \ (k \lt i) 都满足 gcd⁡(i,k)=1\gcd(i,k)=1，那么要保证 b1≠gcd⁡(bk,bj)b_1 \ne \gcd(b_k,b_j)，显然这个式子一定成立，因为 gcd⁡(x,y)≤min⁡(x,y)\gcd(x,y) \le \min(x,y) 且前面条件中保证了只有 b1b_1 能取序列 aa 中的最大值。也就是说，只要 ii 是质数，那么 bib_i 取序列 aa 中的次大值即为最优解。因此根据贪心策略 b3b_3 设置为序列 aa 中次大值。
当 i=4i=4 时，显然对于所有的 j (j>i∧i∣j)j \ (j \gt i \wedge i \mid j) 满足 gcd⁡(4,j)=4\gcd(4,j)=4，那么要保证 b4≠gcd⁡(b4,bj)b_4 \ne \gcd(b_4,b_j)，即保证 ∀j (j∈[8,n]∧i∣j),b4∤bj\forall j \ (j\in [8,n] \wedge i \mid j) , b_4 \nmid b_j。由于 i=4i=4 是合数，因而 bib_i 的取值不能和 bdb_d 的取值相同，其中 d<i∧d∣id \lt i \wedge d \mid i。因而 b4b_4 的最优取值就是序列 aa 中的次次大值。
归纳一下，只要 ii 为质数，那么 bib_i 取序列 aa 中的次大值；若 ii 为合数，则 bib_i 的取值要比 ii 的所有约数 jj 中对应的 bjb_j 的最小值 mnmn 还要小，再根据贪心策略，让 bib_i 尽可能大，即让 bib_i 取序列 aa 中小于 mnmn 的最大值。
具体实现：我们可以将 aa 数组降序排序得到 a′a' 数组，用 ansians_i 记录 bib_i 是取自序列 a′a' 中的哪个下标的值。显然 ans1=1ans_1=1，而对于后续更新过程考虑 DP 转移即可。
ans 数组的 DP 转移方程：ansj=max⁡{ansi+1}ans_j=\max \{ans_i+1 \}，其中 jj 为 ii 的倍数。
那么无解就很好判定了，显然当 ∃i∈[1,n],ansi>m\exist i \in [1,n] ,ans_i \gt m 时无解。
若采用枚举倍数的做法，调和级数时间复杂度 O(nlog⁡n)O(n\log n)。当然也可以线性筛做到 O(n)O(n)。
PS：分析到这你就会发现实际上本题的 ans 数组和给定的 mm 个数毫无关系，ans 数组你完全可以直接预处理。
CPP
const int N=1e5+5;
int n,m;
int a[N];
int ans[N];
void solve(){
	cin>>n>>m;
	rep(i,1,m) cin>>a[i];
	sort(a+1,a+1+m,greater<int>());
	ans[1]=1;
	int mx=0;
	rep(i,1,n){
		for(int j=2*i;j<=n;j+=i){
			ans[j]=max(ans[j],ans[i]+1);
			mx=max(mx,ans[j]);
		}
	}
	if(mx>m) cout<<-1;
	else rep(i,1,n) cout<<a[ans[i]]<<" ";
}

评论

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

正在加载评论...