110

108は想定解を自分で導いて解いたんだけど、どうやって導いたのか忘れてショックだったので、考えはメモっておいた方が良いということがわかった。

n^2のn以下の約数の数が400万を超えるようなnを見つければ良い。そうすると、必ず

2^a * 3^b * 5^c * ... * p

という素数を小さい方から何とか乗して掛け合わせた形になる。途中に空きは無い(3*5*11みたいに7をとばして11が出てくることはない)。空きがあったら、一番大きい数を消して、その空きのところに持ってくれば、約数の数が同じで値が小さいものができあがるというのが理由。

そんな訳で値が小さい順にdijkstraしてみたら答えが出てきました。次の状態への遷移は、現在最大の素因数がp_i^aだとすると、p_i^(a+1)にするか、p_(i+1)^1を追加するかという形。眠いのでこれくらいが限界でしｔ。後でフォーラムみて勉強する。