Codeforces #272 Div1 B. Dreamoon and Sets

Codeforcesお得意のconstructive問題。
http://codeforces.com/contest/477/problem/B

問題

正の整数N,Kが与えられる。

ここでN個の整数の集合を作りたい。これらは以下の条件を満たさなければならない。

• 各集合の要素数は4である。
• 全集合を合わせて、同じ要素は2回使用できない。
• 同じ集合内の任意の2要素の最大公約数はKである。

このような集合のうち、要素の最大値を最小化し、その値と集合の中身を答えよ。

解法

Kの値は無視してよい。
とりあえずK==1のまま集合を作り、全体をK倍すれば解になる。

よって、各集合内が互いに素になるようにしたい。
そこでi番目(0～(N-1))の集合を{6i+1, 6i+2, 6i+3, 6i+5}とするとよい。これらが互いに素になるのは明らか。
また、最大数は6N-1となる。

6N-1未満で解を作れないことを示す。
6N-2までの間に:

1. 6の倍数でない偶数は2N個ある
2. 6の倍数でない３の倍数はN個ある
3. 6の倍数はN-1個ある
4. 偶数でも3の倍数でもない数は2N-1個ある。

N個の集合に2の倍数を1個、3の倍数を1個ずつ入れると、残り使えるのは偶数でも3の倍数でもない数は2N-1個ある。
これらの総和は4N-1なのでN個の集合を満たすことができない。

void solve() {
	int i,j,k,l,r,x,y; string s;
	int N,K;
	
	cin>>N>>K;
	_P("%d\n",K*(N*6-1));
	FOR(i,N) _P("%d %d %d %d\n",K*(6*i+1),K*(6*i+2),K*(6*i+3),K*(6*i+5));
}

まとめ

練習では最初ずっと探索を頑張ってしまった。