yukicoder No.14 最小公倍数ソート

問題

No.14 最小公倍数ソート - yukicoder

サイズNの数列が与えられるので、最左の値との最小公倍数順に最左より右の数列をソートする。
ソートした数列に対してさらに同様の基準でソートする。
これを一番右まで繰り返したときの数列を求める。

解法

単純に考えると、最小公倍数を求めてソートをN回繰り返すので
$O(N*N\log(N))$程度。
少し考えると、毎回ソートする必要はなく、最小値を一番左に持ってきさえすればよいとわかるので
$O(N*N)$となる。
$1 \le N \le 10000$なので、$O(N^2)$なら間に合うらしいのだが、Rubyで愚直にやってみたら全然間に合わなかった。

高速にするため、約数により最小値の選択を効率化する。
一番左の基準値と同じ約数を持つ数のうち、約数で割った値が一番小さい数が、最小公倍数が一番小さい数である。
$最小公倍数=基準値*約数で割った値$ となるため。
また、同じ約数を持つ数字は小さい順にソートしておくことで、約数毎にその約数をもつ一番小さい値を考えるだけで済む。
1も約数として考えるので、全ての数が考慮対象になり、漏れはない。
これで$O(N*\sqrt N)$になる。（約数の個数のオーダーって詳しくは知らないけど、$O(\sqrt N)$以下だよね。）

#7961 No.14 最小公倍数ソート - yukicoder

require'prime'
N=gets.to_i
a=gets.split.map(&:to_i)
div=Hash.new{|h,x|
  h[x]=x.prime_division.inject([1]){|s,(p,k)|
    s+s.flat_map{|i|(1..k).map{|j|i*p**j}}
  }
}
mul=(0..a.max).map{[]}
a.sort.each{|i|
  div[i].each{|d|
    mul[d] << i
  }
}
puts ([i=a[0]]+(2..N).map{
  i=div[i].map{|d|
    mul[d].delete_at(mul[d].index i)
    (t=mul[d][0])?[t/d,t]:[1e9]
  }.min[1]
})*" "