No.14 最小公倍数ソート
問題文最終更新日: 2024-05-04 02:58:35
問題文
最小公倍数を習ったばかりのLarryは、最小公倍数ソートというのを思いついた。
ここで「最小公倍数ソート」とは、
個の整数(重複を含む)が与えられ、それぞれとする。
を固定し、をそれぞれに対して最小公倍数を取り、最小公倍数が小さい順に並べ変えるソートのことであるとする。
(最小公倍数の最小が複数ある場合は、としての値が少ない方が優先される)
Larryは、
この時出来た配列を新たにの名前をつけなおして操作を続ける。
次にを固定し(も固定したまま)、を「最小公倍数ソート」していく。
次にを固定し...と続けていった時にまで行った時になる数列を求めてください。
(C/C++だと愚直な解法でぎりぎり通ってしまいますが、計算量が抑えられる方法があるので★4になってます。)
入力
行目は整数の数を表すが与えられる。
行目は各整数の値を半角スペース区切りとして与えられる。
出力
からまで続けていった時の数列を半角スペース区切りで出力してください。
最後に改行してください。
サンプル
サンプル1
入力
5 1 2 3 4 5
出力
1 2 4 3 5
まず番目のを固定し、それ以降で最小公倍数ソートすると
1 2 3 4 5
次に番目のを固定し、それ以降で最小公倍数ソートすると
1 2 4 3 5
次に番目のを固定し、・・を続けると答えのようになる。
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。