[1]愚直なシミュレーション

この問題は、以下のようにシミュレーションを行うことで解くことが可能です。

• $A_i=\min(\{A_1,A_2,\dots,A_k\})$ を満たす整数 $i$ を $\mathrm{O}(N)$ 時間かけて探索する。
• $A_j=\max(\{A_1,A_2,\dots,A_k\}),i \neq j$ を満たす整数 $j$ を $\mathrm{O}(N)$ 時間かけて探索する。
• $A_j$ を $A_j \bmod A_i$ に変更する。もし $A_j$ が $0$ となったならば削除する。

削除については \(-1\) などを入れておくことにより配列から実際に削除をしなくてもよいため、\(\mathrm{O}(1)\) で行うことができます。

上記の解法は、解を \(X\) としたとき計算量が \(\mathrm{O}(NX)\) となってしまいます。\(1\) 回の操作で \(A\) の長さは高々 \(1\) しか減らないことより、\(X \ge N\) なので実行制限時間に間に合いません。

[2]$X$ の解析

\(X\) を解析します。

\([1]\) でのシミュレーションにおいて、ある要素が \(A_j\) として選ばれる回数を考えます。もし \(1\) 度 \(A_j\) を選んだのであれば、\(\frac{A_j}{2} \ge A_j \bmod A_i\) が成り立つため \(A_j\) は半分未満となります。

よって、ある要素が \(A_j\) として選ばれる回数は高々 \(\mathrm{O}(\log \max A)\) 回です。よって、\(X\) は \(\mathrm{O}(N \log \max A)\) です。

[3]シミュレーションの高速化

シミュレーションを高速化します。まずはじめに \(A\) をソートして \(A_1 \le A_2 \le \dots \le A_N\) とします。その後、以下を繰り返します。

• 現段階での $A$ の長さを $k$ とし、$A$ から $A_k$ を取り出す。
• $A_k \bmod A_1 > 0$ であれば $A$ の先頭に $A_k \bmod A_i$ を挿入する。
• そうでない場合、何もしない。

上記のシミュレーションの過程において、常に \(A_1 \le A_2 \le \dots \le A_k\) が成り立つことが確認できます。

上記の操作は全て両端キューを使うことにより \(\mathrm{O}(1)\) で行うことができます。

よって、本問題を \(\mathrm{O}(X+N\log N)\) で解くことができます。