AGC 022 B - GCD Sequence

• 問題
• AC

$x$と$S \setminus \{x\}$が互いに素でないという条件から偶数の集合$\{2, 4, 6, ...\}$を思い浮かべてみるが、そのままでは$S$の最大公約数が$1$にならないし、また、$30000$までの偶数は$15000$個しかないので数も足りていない。そこで、$3$を加えて$S$の最大公約数を$1$にした上で、$3$の倍数を適当に加えて条件を満たすようにできないか考えてみる。¹

既に特別である集合$S$に、特別性を壊さないように整数を追加することを考える。まず、$S\setminus \{2\}$の総和が$2$で割り切れるようにするために、$S$の中の奇数は常に偶数個を保つべきなので、$3$の倍数で奇数であるものは2個ずつ加えたい:

$(1) \qquad \{3, 9\}, \{15, 21\}, \{27, 33\}, ...$

また、$S\setminus\{3\}$の総和が$3$で割り切れるようにするために、追加する数は常に$3$の倍数を保ちたい。偶数のうち$3$の倍数であるもの、つまり$6$の倍数は1個ずつ加えることが可能である:

$(2)\qquad 6, 12, 18, ...$

偶数のうち$3$の倍数でないもの、つまり$3$を法として$1$または$2$と合同であるものは、ペアで追加すれば$3$の倍数になる:

$(3) \qquad \{2, 4\}, \{8, 10\}, \{14, 16\}, ...$

$(1), (2), (3)$で$20000$個の整数を網羅しているので、あとは$S := \{3, 9\} \cup \{2,4\}$をベースにして$N$に達するまで任意に加えればよい。$N=3$の場合だけ扱えていないが、サンプルにある出力をそのまま使って対応できる。

---

1. 競技としては、$30000$以下の$2$か$3$の倍数である整数がちょうど$20000$個であることからメタ読みもできそう。 ↩︎