大意：求在 \([1, n]\) 中可以表示为 \(m^k\) 形式的数的个数（\(m, k \in \mathbb{Z}^+, k > 1,n \le 10^{18}\)）
这道题不像是有 \(O(1)\) 的解法，但是哪怕是 \(O(\sqrt{n})\) 的算法也会超时，因此直觉上我们应该寻找的是 \(O(\log n)\) 的算法。
首先，因为 \(m = 1\) 的情形是 trivial 的，所以考虑 \(m \ge 2\) 此时 \(k \le \log_m n \le \log_2 n \le 60\)，这也是 \(k\) 的一个上界。
接下来我们发现：如果一个数可以表示为 \(m^4\) 的形式，也一定可以表示为 \((m^2)^2\) 的形式，类似地，如果 \(k = pq\) 是合数的话，那么 \(m^k\) 一定可以表示为 \((m^p)^q\) 和 \((m^q)^p\) 。
令 \(P(i)\) 表示可以表示为 \(m^i\) 形式的数的个数，那么题目显然要我们求的是： \[ \left| \bigcup_{素数 p\le\log_2n} P (p) \right| \] 接下来就用容斥原理很快就能解决这道题了，代码非常的简洁，注意精度：
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const double EPS = 1e-8;
const int p[] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 };
ll n;
ll calc(ll d, ll a) {
if (a > 60) return 0;
if (d == 0)
return a == 1 ? 0 : (ll)(pow(n, 1.0 / a) + EPS) - 1;
return calc(d - 1, a) - calc(d - 1, a * p[d]);
}
int main() {
while (scanf("%lld", &n) != EOF)
printf("%lld\n", -calc(17, 1) + 1);
return 0;
}