CSAcademy Round #43 : E. Coprime Pairs

ちょっと迷ったけどなんとか。
https://csacademy.com/contest/round-43/task/coprime/

問題

2つの整数N,Kが与えられる。
N個の互いに異なる正整数を選び、うち2要素の対が互いに素となるケースがK通りとなるようにせよ。

解法

互いに素なケースではなく、逆に2以上の公約数を持つ対を個作ることを考えよう。
まず、5以上の素数をN個容易する。この時点では2要素の公約数は常に1である。
となる最大のAを求め、N個中A個に2を掛けよう。
そうすると個公約数が2の対を生成できる。
残りは個公約数が2以上の対を生成したいが、残りはA個未満であることは明らかである(A個以上あるなら、そもそもこの前のステップでAをもう1つ大きくできる)。
よって、先ほど2を掛けたA個中個だけ3を掛け、先ほど2を掛けてない要素の1つに3を掛ければ、新規に公約数が3となる対を個生成できる。

ll N,K;

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;
int ret[10101];
void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	cin>>N>>K;
	K=N*(N-1)/2-K;
	
	FOR(i,N) ret[i]=prime[i+2];
	
	ll a=0;
	while(a*(a+1)/2<=K) a++;
	K-=a*(a-1)/2;
	FOR(i,a) ret[i]*=2;
	if(K) {
		ret[a]*=3;
		FOR(i,K) ret[i]*=3;
	}
	
	
	FOR(i,N) _P("%d%c",ret[i],(i==N-1)?'\n':' ');
	
}

まとめ

今回構築ゲー多いな。