[訳注: \(a_n\) が \(f(n)\) と表記されています。]

明らかに、\(f(n)\) はすべて異なります。

素数を昇順に \(p_1,p_2,\cdots,p_k\) と書きます。以下、\(k\) に関する帰納法により、すべての \(u\) に対して \(\frac{f(p_ku)}{f(u)}\) が \(p_k\) 以上の何らかの素因数を含むことと、十分大きな \(N\) に対して \(f(p_k^N)=C_k p_k^N\) であることを証明します。

\(k=1\) の場合は明らかです。\(k-1\) から \(k\) に進むステップでは、\(p_1,p_2,\cdots,p_{k-1}\) の十分大きな累乗を含む \(X\) を考えます。\(\operatorname{LCM}(f(u),f(X))\mid f(uX)\) と \(f(p_ku)\nmid f(uX)\) すなわち \(\frac{f(p_ku)}{f(u)}\nmid \frac{f(uX)}{f(u)}\) から、\(\frac{f(p_ku)}{f(u)}\) が \(p_{k-1}\) より大きい素因数を含むことがわかります。主張の後半は、いま \(f(p_k^{N+1})\ge p_kf(p_k^N)\) といえることに注意すると、ここで「>」が \(\log_{p_{k+1}/p_k}C\) 回以下しか成立しないことから証明されます。

上記の帰納法により、\(v_p(x)>v_p(y)\) なら \(v_p (f(x)) > v_p (f(y))\) であることがいえます。そうでないなら、\(p\) を除く \(f(x)\) の素因数の十分大きな累乗を含む \(Z\) を選ぶと、\(f(x)|f(yZ)\) かつ \(x\nmid yZ\) で矛盾します。 入力された数が約数条件に反していない限り、この条件は十分でもあります。これの証明は単純です。\(x\nmid y\) に対しては、\(v_p(x)>v_p(y)\) であるような素数 \(p\) を考えると \(f(x)\nmid f(y)\) がいえます。すべての \(x\mid y\) に対して \(f(x)\mid f(y)\) とするには、以下のように構築します。各素数と各「層」（\(v_p(x)\) が一定であるような数 \(x\) たち）に対し、その中で最大の \(p\) の累乗を採用します（空の層に対しては、存在しない最小の整数を採用して統一だけします）。

すべてを愚直に確認しても \(O(n\log (\max a_i)+n \pi (n))\) 時間で済みます。