TopCoder SRM 683 (Div. 1) Med. GCDLCM2

cnt[i] の上限が 10⁵ だと勘違いしていてまともに考察ができなかった。

解法

まず擬似コード通りに数を生成し、これを改めて数列 a[n] とする。

gcd(a,b)+lcm(a,b)≧a+b が成り立つので操作はできるだけ行った方がよい。 それでは操作をできるだけ行ったときの最終形はどのようになるだろうか。

a[i] の素数の個数のテーブルを考えてみる。a[2] と a[3] に操作を行うと次のような変化を見せる。

要するに、両者の素数の個数のうち小さい方を左に、大きい方を右に移動させる操作になっている。

この操作を何度も行えば最終的に次のような状態になる。

それぞれの素数の個数を見てあげると昇順になっていることがわかる。

ここまで分かれば後は実装するのみ。

---

素因数分解は愚直にやっても間に合う。

TopCoder SRM 683 (Div. 1) GCDLCM2

和の制約や積の制約のような特殊な制約には気をつけたい。 10^5 の配列をそのまま渡してくれれば n と a[i] の上限の制約だけなはずなんだけど難しいんだろうか。