\(N=1\) のときは \(A=(1)\) が条件を満たします。\(N=2\) のときは、条件を満たす \(A\) は存在しません。以下、\(N \ge 3\) とします。

\(\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}\) であることを利用すると、\(A\) を \((2,6,12,20,\dots,N(N-1),N)\) にすることで総和の条件を満たすことが出来ます。

ですが、このままだと \(N=k(k-1)\) と表せる際に \(A\) の要素に重複が生じてしまいます。例えば、上記の構築だと \(N=6\) のときに \(A=(2,6,12,20,30,6)\) です。これを対処しましょう。

これは \(N\) を \(1\) 減らしたときの答え \(A'=(A'_1,A'_2,\dots,A'_{N-1})\) に対して \(A=(2,2A'_1,2A'_2,\dots,2A'_{N-1})\) を用いることで解決します。この整数列 \(A\) が条件を満たすことを確認しましょう。

• \(\sum_{i=1}^{N-1} \frac{1}{2A'_i} = \frac{1}{2}\) であるため、\(\sum_{i=1}^{N} \frac{1}{A_i} = 1\) を満たします。
• \(A'\) は \(1\) を明らかに含まないため、\(2\) と \(2A'_i\) が一致することはありません。また、\(A'\) の要素は全て相異なるため、\(A\) の要素も全て相異なります。
• 整数 \(k\) を用いて \(k(k-1)\) と表せる整数は連続しないため、\(A'\) は \((2,6,12,20,\dots,(N-2)(N-1),N-1)\) です。これを \(2\) 倍しても明らかに \(10^9\) を超えないため、全ての要素は \(1\) 以上 \(10^9\) 以下です。

よって、\(A'\) がすべての条件を満たすことを確認できました。

上記を実装することにより、この問題を \(\mathrm{O}(N)\) で解くことが出来ます。

要素の重複があった場合、約分を行うことで重複をなくし、長さを \(N\) にするために最後の要素を \(\frac{1}{2} = \frac{1}{3} + \frac{1}{6}\) などを用いて分割する解法でも解くことが出来ますが、\(N=12,420\) のときに \(\frac{N}{2}\) も \(k(k-1)\) の形で表せてしまうため約分を複数回行う必要があることに注意してください。