A. Kids Seating (Codeforces Round #681 Div. 2)

これはこどふぉDiv. 2のAにありがちなギャグではなく、制約の意味を考えるいい問題なのではと思いました。

問題

https://codeforces.com/contest/1443/problem/A

問題概要

整数nが与えられる。1から4nまでの数を一つずつ持った集合の部分集合として、要素をn個持った集合を作れ。ただし、作った集合の任意の2つの要素について以下の性質を満たさなければならない。

• GCDが1ではない
• どちらかがもう一方を割り切ってはいけない

考察

私は、まず2*p (pは素数)という数を{2*2, 2*3, 2*5, 2*7, ...}という具合にn個並べることを最初に思いつきました。お互いのGCDは2になるし、それぞれ別の素数を因数に持っているので割り切ることもできないからです。

しかしこれは4nまでの数という制約のもとでは成立しません。2*p<=4nを満たさなければならないため、pは2n以下の数でなければならず、その範囲で素数がn個なければならないですが、例えばn=100のとき200以下に素数は100個もないからです。

ここで、4nという制約の意味を改めて考えます。4nより小さい数字で4nを割り切れる最大の数字は2nです。2 * 2nなので。したがって、2nより大きい数を選べば割り切ってはいけないの条件は満たすことができます。

そして、2nより大きく4n以下の数字で、かつ2の倍数（4nとのGCDが1にならない）がいくつあるかというと、4nまでの2の倍数は2n個、2nまでの2の倍数はn個なので、ちょうどn個なんですねこれが。

というわけで、2nより大きく4n以下の数字で、かつ2の倍数をn個（全て）並べたものが答えとなるのでした。

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, (n))
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int m = n * 4;
        REP(i, n) {
            cout << m << (i == n - 1 ? '\n' : ' ');
            m -= 2;
        }
    }
}