\(1\) は条件を満たします。それ以外で条件を満たす数が何個あるかを考えます。

\(2\) 以上の正整数 \(c, d\) を用いて、 \(a = c ^ {d}\) と表せない \(2\) 以上 \(N\) 以下の整数 \(a\) を 悪い整数 とします。

悪い整数 全てにおいて、\(\lfloor\log_{a}(N)\rfloor - 1\) の総和が求まれば良いです。

\(N < a^{2}\) のときは、\(\lfloor\log_{a}(N)\rfloor - 1 = 0\) です。

\(a ^{2} \leq N < a^{3}\) のときは、\(\lfloor\log_{a}(N)\rfloor - 1 = 1\) です。

よって、\(a ^{3}\leq N\) を満たす全ての 悪い整数 において、\(\lfloor\log_{a}(N)\rfloor - 1\) の総和を求めた後、\(a ^{2} \leq N < a^{3}\) を満たす悪い整数 の総数を求めることができれば良いです。

これは、\(a ^{2} \leq N < a^{3}\) を満たす整数が \(a = c ^ {d}\) と表せるとき、\(c < a ^ {1.5} < a^{2}\) を満たすことから、\(2 < c ^{3}\leq N\) を満たす整数 \(c\) を全探索すれば良いです。

より正確な記述は実装例をご覧ください。std::vector good という配列で、 \(\sqrt[3]{N}\) 以下の整数が 悪い整数か否かを管理しています。

計算量は \(O(N ^{\frac{1}{3}})\) に近いとは思いますが、正しくはわかりません。

実装例 c++ 11ms