基本的には大きな \(N\) に対する構築ほど難しいので、\(N\) を大きくする方法について考えます。

◆基本方針

集合 \(A = \{a_1,\ldots,a_n\}\) が条件を満たすならば、\(a_i\) の倍数をさらに \(A\) に追加しても、再び条件を満たすことが分かります。

例えば、【出力例1】の \(A = \{84, 60, 105, 70\}\) から始めることにします。この集合に \(84\) の倍数や \(60\) の倍数を追加していっても再び条件を満たします。この操作を最大限行うと、「（\(1\) 以上 \(10000\) 以下の）\(84,60,105,70\) いずれかの倍数全体」として、\(N = 429\) が達成できます。

◆解答例

\(A = \{84,60,105,70\}\) から始めると \(N = 429\) が達成できましたが、始状態の集合 \(A\) を洗練させれば、より大きな \(N\) が実現できます。

• (writer 解法)：\(6, 10, 15\) いずれかの倍数全体として、条件を満たす \(2666\) 元集合が実現できる。
• (tester 解法)：\(6, 10, 14, 22, 1155\) いずれかの倍数全体として、条件を満たす \(2926\) 元集合が実現できる。

このような集合から、全体が互いに素になるような \(N\) 元部分集合を出力すればよいです。

【解答例】 https://atcoder.jp/contests/arc118/submissions/22269560 （Python, \(N \leq 2666\)）