专栏文章

题解：CF1208G Polygons

ttangible_love
CF1208G题解参与者 1已保存评论 0

文章操作

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

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

思路

对其他题解的补充。可以配合食用。
很巧妙的题目。拿到题显然考虑类似于反悔贪心的思路：先从小到大加，如果出现不优的方案就进行替换来寻找规律。
那么容易发现对于 xx 边形，xx 的因子（不包括 xx，11，22）来说，它们一定是可以在 xx 边形里面画出来的。又有一个性质 ∑x∣yϕ(x)=y\sum_{x|y} \phi(x) = y ，所以我们可以根据这个东西来处理在从 11 到 nn 挨着加时候的去重部分。对于 ii 边形而言，它的因子的 ϕ\phi 都已经算过了，对于它就只用算 ϕ(i)\phi(i) 了。这就是为什么 ii 的贡献是 ϕ(i)\phi(i)。
回到题目本身。既然跟 ϕ\phi 有关就线性筛先处理出所有 11 到 nn 中的 ϕ\phi 值。按这个从小到大排序。发现一个性质：如果选择了 xx 的倍数，一定选了 xx，因为 ϕ(xi)≥ϕ(x)\phi (xi) \ge \phi(x)，所以 xx 肯定在之前就被选择了。
那么我们取前 kk 个一定满足题目，因为算贡献的时候肯定是把每一个都算进去了，可以用上面的性质证明。
在特判的时候考虑 k≤2k \le 2 的情况即可，就是三角形和四边形。

代码

CPP
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,k,len,ans,pri[1000010],phi[1000010];
bool vis[1000010];
signed main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			pri[++len]=i;
			phi[i]=i-1;
		}
		for(int j=1;i*pri[j]<=n;j++){
			vis[i*pri[j]]=true;
			if(i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
			else{
				phi[i*pri[j]]=phi[i]*pri[j];
				break; 
			}
		}
	}
	sort(phi+1,phi+1+n);
	for(int i=3;i<=k+2;i++) ans+=phi[i];
	cout<<ans+1+(k!=1);
	return 0;
}

评论

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

正在加载评论...