还没有睡着的各位OIer给个思路行嘛Q^Q

Question

题目描述
给一个整数n，在1~n之间有多少整数不能表示为pow( a ,b )(a 的b 次幂)的形式，其中a,b不小于2.

数据范围：1<=n<=10^10

vickyの opinion：
一开始我想的是遍历每个数，但后面我发现这个数据范围直接out掉了遍历，遍历2.5*10^7就已经1s了，更何况遍历10^10次呢 QAQ
随后我便开始猜想其中是否有什么规律，但是在考场找了一个多小时的规律，回家又找了半个小时，啥也没找到……
求思路Q^Q

Answer 1

1、首先a的b次幂，b>=2的话，底数a的范围就是在 [2, 根号N] 之间的整数，所以只要遍历这些底数，大概是10的5次方。
2、其次a的b次幂要小于等于N，那么对于每一个底数a，指数b的范围就是在 [2，log(N)/log(a)] 之间的整数，这里不需要遍历，可以直接求出满足条件的数的个数 floor( log(N)/log(a) - 2 +1)。
3、用 N减去满足条件的数的个数，就得到你想要的结果了。