题意
求 \(1\) ~ \(n\) 中有多少数 \(x\) 可以写成 \(x=a^b\) 的形式（其中 \(b\ge 2\)）
\(n\le 10^{18}\)
容斥
显然 \(1\) 是可以写成 \(1^b\) 的，我们单独讨论这种情况，以下默认 \(a\ge 2\)
发现一个数有可能有很多种 \(a^b\) 的写法，比如 \(64=2^6=4^3=8^2\)
显然当 \(b\) 不是质数时，就一定可以把 \(b\) 拆得更小，即 \(x=a^b=(a^p)^{\frac{b}{p}}\)。所以我们不妨忽略 \(b\) 不是质数的情况，即只统计 \(a^p\)（\(p\) 为质数）。
对于一个 \(b\)，有 \(a=2,3,\dots,\lfloor\sqrt[b]{n}\rfloor-1\) 使得 \(a^b\) 符合题意。
但是答案并不是所有 \(\lfloor\sqrt[b]{n}\rfloor-1\) 之和，比如 \(b=2\) 和 \(b=3\) 时，都会统计到 \(x=64=8^2=4^3\)，所以我们考虑容斥。
- 先加入 \(b=p_i\) 的情况，即 \(a^2,a^3,a^5,\dots\)
- 再除去 \(b=p_ip_j\) 的情况，即 \(a^{2\times 3},a^{2\times 5}\dots\)
- 再加入 \(b=p_ip_jp_k\) 的情况
- \(\dots\)
其中 \(b\) 的容斥系数与其质因数个数有关，且含平方因子的 \(b\) 系数为 \(0\)。不难发现这就是 \(-\mu(b)\)，所以最后答案为
\[1-\sum\limits_{b=2}^{\log_2{n}}\mu(b)\cdot(\lfloor\sqrt[b]{n}\rfloor-1) \] 标签：dots,lfloor,rfloor,质数,容斥,sqrt,反演,ABC361F From： https://www.cnblogs.com/hzy1/p/18325949