問題URL
考察
・全探索............無理............DP............無理............
・ $a$ との積が立方数になる数はどんな数だろう？
・ $2$ との積が立方数になる数...
$4$
$32$
$108$
$256$
:
・全部 $4$ の倍数だ
・ $4$ で割ると $1, 8, 27, 64...$ 立方数じゃん！
・ $2 \times 4 \times $ (立方数) は $8 \times $ (立方数) になるから立方数になるのか
・だったら $p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ との積が立方数になる数は $p_1^{3-e_1}p_2^{3-e_2}...p_k^{3-e_k}$ であればいいのか
・ん、これじゃ $16$ の時とかに対応する数が $1/2$ になっちゃうな
・ $p_1^{3-e_1 \mod 3}p_2^{3-e_2 \mod 3}...p_k^{3-e_k \mod 3}$ か
・これだと $8$ の時に対応する数が $1$ じゃなくて $8$ になる
・だったら $p_1^{2-(e_1+2) \mod 3}p_2^{2-(e_2+2) \mod 3}...p_k^{2-(e_k+2) \mod 3}$
・全ての $s_i$ についてこれが5秒以内に求められるか？
・素因数分解に $O(\sqrt{s_i})$ だから計算量は $O(\displaystyle\sum_{i=1}^N\sqrt{s_i})$ になって間に合わない
・とりあえず「 $s_i$ から立方数を取り除く(＝ $e_i \mod 3$ を求める)パート」と「 $s_i$ から立方数を取り除いた後、積が立方数になる数を求めるパート」に分けて考えよう
立方数を取り除くパート
・素因数分解と同じように、小さい立方数から割っていけばいい
・ $s_i$ までの立方数で割ればいいから、割るべき立方数の個数は $\sqrt[3]{s_i}$ 個程度
・計算量は $O(\displaystyle\sum_{i=1}^N\sqrt[3]{s_i})$ になる
・これだと最悪で $3.1\times10^8$ 程度になるからギリギリだ
・改善できないか？
・ (素数)$^3$ で割れるだけ割る、という方法が使えそう
・ $\sqrt[3]{s_i}$ 以下の素数をエラトステネスの篩であらかじめ列挙しておけばいい(計算量は $O(\sqrt[3]{s_i}\log\log\sqrt[3]{s_i})$ )
・素数の密度は素数定理より $\log_e \sqrt[3]{s_i}=\frac{1}{3}\log_e s_i$ 程度なので、立方数を取り除くパートの計算量は $O(\sqrt[3]{\max(s_1, s_2, ... s_N)}\log\log\sqrt[3]{\max(s_1, s_2, ... s_N)}+\displaystyle\sum_{i=1}^N\frac{\sqrt[3]{s_i}}{\log{s_i}})$ で間に合う
積が立方数になる数を求めるパート
・立方数を取り除いた $s_i$ を $P_1^{E_1}P_2^{E_2}...P_k^{E_k}$ として、 $P_1^{3-E_1}P_2^{3-E_2}...P_k^{3-E_3}$ を求める ( $E_i=1,2$ )
・ただ素因数分解をする → $O(\displaystyle\sum_{i=1}^N\sqrt{s_i})$ → 間に合わない！
・あらかじめ素数を列挙して、素数だけで割って素因数分解をする → $O(\displaystyle\sum_{i=1}^N\frac{\sqrt{s_i}}{\log{s_i}})$ → 間に合わない！
ここまで書いたんですが、次の話(Code内の83行目〜91行目)に対する説明が難しすぎたのでここで諦めます
Code → https://beta.atcoder.jp/contests/agc003/submissions/2413701