「CF1208G」 Polygons

「CF1208G」 Polygons

似乎我校神犇在很久以前和我提过这题？

首先有一点显而易见：这 (k) 个多边形肯定至少有一个公共的顶点。假设我们将此点定义为起点。

那么对于一个正 (n) 边形，每一条边所截的短弧所对应的圆心角大小相等，所以我们可以把顶点标记为 (frac{1}{n},frac{2}{n},frac{3}{n},cdots,frac{n}{n})。

那么有结论：对于任意一个正 (n) 边形的顶点，当且仅当顶点标号为一个最简分数时才会被统计进答案。

证明也很简单，假设存在一个正 (n) 边形顶点标号为非最简分数被统计进答案，那么将标号化为最简分数后其所对应的正多边形我们一定没有选择。但是显然这个正多边形的点数比我们刚才选择的正 (n) 边形要少，这与题目要求相悖，故假设不成立。

因为 (nge 3)，所以有两个顶点没有被我们统计到：(frac{1}{2} , frac{n}{n}) 。

考虑特判：

• 当 (k=1) 时我们一定会选择正三角形，其包含 (frac{n}{n})。

• 当 (k=2) 时我们可以选择正三角形和正四边形，其包含 (frac{1}{2} , frac{n}{n})。

• 当 (kge 3) 时由于已经选择了正三角形和正四边形，未统计的两个顶点已经统计，所以不受影响。

考虑对一个正 (n) 边形统计这样的最简分数，很显然可以发现答案就是 (varphi(n))。所以我们选择从 (varphi(5)) 开始的前 (k) 大的欧拉函数值即可。

总时间复杂度为 (O(nlog_2n))，使用基数排序可优化至 (O(n))。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int p[maxn],pri[maxn],phi[maxn],cnt;
int n,k;
int init(){
	phi[1]=1;
	for(int i=2;i<=n;++i){
		if(!p[i]){
			pri[++cnt]=i,phi[i]=i-1;
		}
		for(int j=1;j<=cnt&&pri[j]*i<=n;++j){
			p[pri[j]*i]=1;
			if(i%pri[j]==0){
				phi[pri[j]*i]=phi[i]*pri[j];
				break;
			} 
			else phi[i*pri[j]]=phi[i]*(pri[j]-1);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	if(k==1) cout<<3<<'
',exit(0);
	if(k==2) cout<<6<<'
',exit(0);
	init();
	sort(phi+5,phi+n+1);
	long long ans=6;
	for(int i=5;i<=5+k-2-1;++i) ans+=phi[i];
	cout<<ans<<'
';
	return 0;
}