ABC193C - Unexpressed

むずい．考えの流れを整理しておく．
【類題】

• C - ABC conjecture

考え方

$N\leq 10^{10}$だから，$N$になる数を調べることはできない．よって，$a^{b}$で表せる数を重複なくカウントして，$N$から引く方針．

一番単純な方法として，「$a,b$の全探索＋setの利用」が考えられる（うまくいく気がしないと思って，この前探索を諦めてはダメ！）．この計算量を真面目に考える．

まず，$a$の範囲を考える．$b \geq 2$だから，$a^{2} \leq a^{b} \leq N$より$a \leq \sqrt{N} \leq 10^{5}$となる．よって，$b$の探索範囲が小さければ，全探索できる．

$b$の範囲を考える．$a\geq 2$を固定したとき，$ a^{b} \leq N$より

\begin{aligned}
b
& \leq \frac{\log(N)}{\log(a)} \\
& \leq \frac{10 \log 10}{\log 2} (\simeq 33.2)
\end{aligned}

だから，$b$の探索範囲は狭い (Divide[10 log 10,log 2] - Wolfram|Alpha)．

※ $a=2$の場合が$b$の探索範囲が一番広くなる．$2^{10} =1024$より大体$2^{30}\sim 10^{9}$のように考えれば，もっとざっくり考察できる．

回答例

N = int(input())

memo =set()
a = 2
while a <= 10 ** 5:
  b = 2
  while True:
    c = a ** b
    if c > N:
      break
    memo.add(c)
    b += 1
  a += 1

print(N - len(memo))