4216: Unexpressed

# Unexpressed ### 内存 1024MB ### 时间 2S ## 题目描述 给定一个整数 $N$。在 $1$ 到 $N$（包括 $1$ 和 $N$）之间有多少个整数不能表示为 $a^b$ 的形式，其中 $a$ 和 $b$ 都是不小于 $2$ 的整数？ ## 输入格式 输入$N$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 8 ``` ### 输出样例1 ``` 6 ``` ### 输入样例2 ``` 100000 ``` ### 输出样例2 ``` 99634 ``` ## 数据范围与提示 【样例1说明】 4 和 8 可以表示为 $a^b$ 的形式：我们有 $2^2 = 4$ 和 $2^3 = 8$。 另一方面，1、2、3、5、6 和 7 不能用不小于 2 的整数 a 和 b 表示为 $a^b$ 的形式，所以答案是 6。 【数据范围】 $N$ 是一个整数 $1 \leq N \leq 10^{10}$ ## 题目来源 ABC193C