No.14 最小公倍数ソート

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 94
作問者 : yuki2006yuki2006
11 ProblemId : 38 / 出題時の順位表
問題文最終更新日: 2020-01-03 16:05:59

問題文

最小公倍数を習ったばかりのLarryは、最小公倍数ソートというのを思いついた。

ここで「最小公倍数ソート」とは、
\(N\)個の整数(重複を含む)が与えられ、それぞれ\(a_i\ (1 \leq i \leq N)\)とする。
\(a_1\)を固定し、\(a_2〜a_N\)をそれぞれ\(a_1\)に対して最小公倍数を取り、最小公倍数が小さい順に並べ変えるソートのことであるとする。
(最小公倍数の最小が複数ある場合は、元の数が少ない方が優先される)

Larryは、
この時出来た配列を新たに\(a_1 \dots a_N\)の名前をつけなおして操作を続ける。
次に\(a_2\)を固定し(\(a_1\)も固定したまま)、\(a_3〜a_N\)を「最小公倍数ソート」していく。
次に\(a_3\)を固定し...と続けていった時に\(a_N\)まで行った時になる数列を求めてください。

(C/C++だと愚直な解法でぎりぎり通ってしまいますが、計算量が抑えられる方法があるので★4になってます。)

入力

\(N\)
\(a_1\ a_2\ \dots\ a_i\ \dots\ a_N\)

\(1\)行目は整数の数を表す\(N\ (1 \leq N \leq 10000)\)が与えられる。
\(2\)行目は各整数の値\(a_i\ (1 \leq i \leq N, 1 \leq a_i \leq 10000)\)を半角スペース区切りとして与えられる。

出力

\(a_1\)から\(a_N\)まで続けていった時の数列を半角スペース区切りで出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5
1 2 3 4 5
出力
1 2 4 3 5

まず\(1\)番目の\(1\)を固定し、それ以降で最小公倍数ソートすると
1 2 3 4 5
次に\(2\)番目の\(2\)を固定し、それ以降で最小公倍数ソートすると
1 2 4 3 5
次に\(3\)番目の\(4\)を固定し、・・を続けると答えのようになる。

サンプル2
入力
5
4 8 1 2 4
出力
4 1 2 4 8

同じ数が出てくる可能性もあります、ソート時に同じ最小公倍数だったら、元の数が少ない方を優先します。

サンプル3
入力
10
9 9 3 7 5 9 1 5 2 1
出力
9 1 1 2 3 9 9 5 5 7

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。