\(N\) を \(2\) 以上の整数とします。

[1] \(N\) が素数のべき乗の場合

\(N=p^e\ (1\leq e)\) と置けます。

まず \(2 \leq n\) であることから\(A_i < N\) が必要です。また、\(N\) が \(A_i\) の最小公倍数であることから \(A_i\) は \(N\) の約数であることが必要です。

上記の考察から \(A_i\) は \(p^k\ (k < e)\) のいずれかになりますが、これらは \(p^{e-1}\) の約数であるため、最小公倍数は \(p^{e-1}\) 以下となります。

よって条件を満たす \(A_1,A_2,\dots,A_n\) は存在しません。

[2] \(N\) が素数のべき乗でない場合

\(N\) が素数のべき乗でない場合、\(N\) は \(6\) 以上の整数であり、\(N\) は相異なる素因数 \(p,q\ (p\neq q)\) を持ちます。

このとき、\(k=N-\frac{N}{p}-\frac{N}{q}\ (\geq N - \frac{N}{2} -\frac{N}{3} = \frac{N}{6} > 0)\) として

\((A_1,A_2,\dots,A_{k},A_{k+1},A_{k+2})=(\underbrace{1,1,\dots,1}_{k},\frac{N}{p},\frac{N}{q})\)

とすると条件を満たします。

以上の考察から \(N\) が素数のべき乗であるかが判定できればよく、これは \(N\) の素因数分解が求まればいいです。

\(N\) の素因数分解は試し割り法により \(O(\sqrt{N})\) で求まり、十分高速です。