Odd Numbers of Divisors (SPOJ 3107)

https://www.spoj.pl/problems/ODDDIV/

問題

奇数kが与えられる。lowからhighの範囲で約数がちょうどk個ある数値の数を答えよ。
1

解法

前提として、約数の個数は奇数なので素因数分解したときに素数piは偶数個しかなく、素因数分解した際に大きな素数が残ることは無い。
なので、エラトステネスの篩で10^5までの素数を全て生成し、10^10までの数値で約数が奇数個だけ含まれる数値を全て列挙しておいて、各テストケースに対して答えを出力してやれば良い。なおsetだとO(logn)以下で区間に入る数値の個数を調べることができなかったので、数値を全て列挙した後にsetを配列に落として計算した。