問題一覧 > 通常問題

No.14 最小公倍数ソート

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 137
作問者 : yuki2006yuki2006
15 ProblemId : 38 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-04 02:58:35

問題文

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

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

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

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

入力

NN
a1 a2  ai  aNa_1\ a_2\ \dots\ a_i\ \dots\ a_N

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

出力

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

サンプル

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

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

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。