Codeforces #632 Div2 F. Kate and imperfection

AC数がDと同水準…。
https://codeforces.com/contest/1333/problem/F

問題

正整数の集合Mを考える。Mの不完全さとは、M中の異なる2要素のgcd(a,b)のうち最大値とする。

整数Nが与えられる。
I[k]を以下のように定義する。

• 1～Nのうちk要素からなるMの取り方のうち不完全さの最小値

k=2～NについてI[k]を求めよ。

解法

kの大きい順に求めて行く。
今仮にI[k+1]=pがわかっているとき、I[k]がどうなるか考えよう。
1～Nのうち、まだMに残っている整数の集合を考える。

• pの倍数が2個以上あるなら、最大値をMから取り除こう。
• pの倍数が1個以下なら、gcdはpになりえないので、pをデクリメントして処理を繰り返す

このようにして更新したpがI[k]となる。

int N;

int alive[505050];
int ret[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) alive[i]=1;
	int cur=N/2;
	for(i=N;i>=2;i--) {
		
		ret[i]=cur;
		int del=0;
		while(cur>1) {
			int num=0,ma=0;
			for(x=cur;x<=N;x+=cur) if(alive[x]) num++, ma=x;
			
			if(num>1) {
				if(del==0) {
					alive[ma]=0;
					del=1;
				}
				else {
					break;
				}
			}
			else {
				cur--;
			}
		}
	}
	
	for(i=2;i<=N;i++) _P("%d ",ret[i]);
	_P("\n");
}

まとめ

Div2Fにしては軽いよね。