Greater Sort

$a_i$の最大の素因数は$O(\sqrt{a_i})$で求めることができますが、制約上$O(a_i)$でも可能です。

$a_i$の最大の素因数を求めた後、問題文の通りにソートする方法はいくつかありますが、ここでは$1$つのみ紹介します。

$a_i$の最大の素因数を$m_i$とおきます。$X$として十分大きな値を取り、$b_i = m_i \times X + a_i$を満たす配列$b$をつくります。 $b$を昇順にソートすることで$m_i$の小さい順に、$m_i$が等しい場合は$a_i$の小さい順に並べることができます。 最後に、$b_i$を$X$で割った余りに置き換えることで、求める配列を得られます。 そのため、$X$はすべての$a_i$に対して真に大きい必要があります。