[AGC022] B - GCD Sequence

[Q] https://atcoder.jp/contests/agc022/tasks/agc022_b

なぞなぞ。いろいろ考察した結果、4ルールを守る。
0. 偶数(6の倍数じゃない)と奇数(3の倍数)を最低1個ずつとる。// 全GCD=1にする
1. 奇数は3の倍数だけ。
2. 奇数(3の倍数)を選んだ時に、偶数の総和が3で割れること
3. 偶数(2の倍数)を選んだ時に、奇数の総和が2で割れること

Q. 取得する優先順位、どうしよう？
A. この順番で実装。

0.
N = 3,4 はサンプル投げちゃえばいい。
N >= 5 を考える。

1. 
偶数を選ぶときに、奇数の総和が2の倍数じゃないといけないので、
3の倍数をとるときは、
3,9 がセット。
15,21 がセット。
27,33 がセット...
と、2個ずつ取る。

2. 
奇数を選ぶときに、偶数の総和が3の倍数じゃないといけないので、
2,4 がセット。
8,10 がセット。
14,16 がセット...
と2個ずつとる。(6で割って2,4あまるものをセット)

3. 
6の倍数は、単体でとっていい。
6 は入れても入れなくてもいい。
12 は入れても入れなくてもいい。
18 は入れても入れなくてもいい...

4. すべてのGCDを1にするために、とりあえず
{2, 3, 4, 9}
は確定で入れる。

実装

int main(){
 cincout();
 
 ll N;
 cin >> N;
 
 if (N==3){
   cout << "2 5 63" << endl;
   return 0;
 }
 if (N==4){
   cout << "2 5 20 63" << endl;
   return 0;
 }

 vector<ll> ans;
 ans.push_back(2);
 ans.push_back(4);
 ll n = N-2;
 // 3の倍数を2個ずついれる
 for(ll i=3; i<=30000; i+=12){
   if (n<=1) break;
   ans.push_back(i);
   ans.push_back(i+6);
   n-=2;
 }
 // 2,4を2個ずつ入れる
 for(ll i=8; i<=30000; i+=6){
   if (n<=1) break;
   ans.push_back(i);
   ans.push_back(i+2);
   n-=2;
 }
 // 6の倍数入れる
 for(ll i=6; i<=30000; i+=6){
   if (n==0) break;
   ans.push_back(i);
   --n;
 }
 
 sort(all(ans));
 ll pre = 0;
 rep(i, N){
   assert(pre!=ans[i]);
   cout << ans[i];
   if (i == N-1) cout << endl;
   else cout << " ";
   pre = ans[i];
 }
}

https://atcoder.jp/contests/agc022/submissions/28588550