ABC193 C問題

C - Unexpressed

要約

N以下のa^bを満たすa, bの組み合わせを

for a in range(N):
  for b in range(N)

みたいな二重ループで探していくと当然計算量が最悪O(N^2)となりTLEになってしまう．そこで何かしらの工夫を考えていく

方針

まず基本的な考え方としては，N以下のa^bと表される数を数え上げて，その個数をNから引けばいい．

ここで実際の遷移をa方向とb方向で見ていくと，aは一番大きくても√nになることがわかる．これにより，a方向のループをO(√n)にできる．

このまま進めていけば良いように感じれるがもう一つ問題があり，

2^4 = 4^2 = 16

のような被りが起こる問題である．これはpythonであれば，set型を使えば解決できる．set型では重複を許さない形でリストを扱えるため楽である．

N = int(input())
import math
memo = set() #重複を許さないset型
#print(math.sqrt(N))
for a in range(2, math.ceil(math.sqrt(N))+1):
 #print(a)
 for b in range(2, int(1e10)): #年のため範囲をバカでかく取っておく
   z = a ** b
   #print(z)
   if z <= N:
     #print(z)
     memo.add(z)
   #Nを越したら次のaを考える
   else:
     break
print(N - len(memo))