SRM643Div1Easy

問題

大きな整数Nが与えられる。これを素因数分解した時の昇順にならんだ因数の数列を求めたい。ヒントとして答えとなる数列の偶数番目の要素(初めのインデックスは0)を取り出した数列が与えられる。

解法

愚直に素因数分解をすると $O(\sqrt{N})$ となるため、計算量を削る必要がある。
答えとなる数列の要素が奇数の場合最大の因数が答えに含まれ、偶数の場合は2番目に大きい因数が含まれる。ヒントに含まれていない一番大きい因数を求めようとすると計算量が $O(\sqrt{N})$ となってしまうので、ヒントに含まれていない二番目に大きい因数を求めるようにする。
二番目に大きい因数をpとする。答えとなる数列の要素が偶数の場合は $p*p*p \leq N$ を満たし、
奇数の場合は $p*p*p*p \leq N$ を満たす。よって、 $O(\sqrt[3]{N})$ で答えが求まる。