Manthan Codefest 19 : G. Polygons

意外にコードは短い。
https://codeforces.com/contest/1208/problem/G

問題

円の円周上にいくつか点を打ち、そこからいくつかを結ぶことで、正3～N多角形のうち異なるK個を構築したい。
各点は複数の多角形で複数回利用されていてもよい。
最少で何個の点が必要か。

解法

L角形を構築するとき、当然ながらその約数のM角形は先に構築されていた方がよい。
と考えると、ある多角形を構築するにはφ(L)個の点を追加する必要がある。
そこで、φ(3)～φ(L)のうち小さい順にK個選ぼう。

int N,K;
int did[1010101];
ll num[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	if(K==1) return _P("3\n");
	
	vector<int> V;
	FOR(i,N+1) num[i]=i;
	for(i=2;i<=N;i++) if(did[i]==0) {
		for(j=i;j<=N;j+=i) did[j]=1, num[j]=num[j]/i*(i-1);
	}
	
	ll ret=2;
	for(i=3;i<=N;i++) V.push_back(num[i]);
	sort(ALL(V));
	FOR(i,K) ret+=V[i];
	cout<<ret<<endl;
	
}

まとめ

これは本番に解いておきたかったな…。