P9118

首先特判 $k=1$，令 $f(n)$ 表示 $[1,n]$ 能表示为 $x=a^b$ 形式的整数 $x$ 个数，其中 $a\ge 1,b\ge 2$，那么答案可以简单表述为 $$f(n)-\sum_{i=2}^{k-1}f(\lfloor\sqrt[i]{n}\rfloor)$$ 于是只需要快速计算 $f$，也就是 $k=2$ 的情况 . 考虑对指数容斥，首先如果一个指数不是 square-free 的，那么可以直接忽略它产生的贡献，那么只需要考虑 square-free number 作为指数的情况 . 有 $a^{pq}=(a^p)^q=(a^q)^p$，于是如果指数 $e$ 有 $k$ 个不同的素因子，那么其容斥系数就是 $(-1)^{k+1}$ . 综合上述内容，即可得出容斥系数即为 $-\mu(e)$，则可以写出 $f$ 的表达式： $$f(n)=1-\sum_{i\ge 2}\mu(i)(\lfloor\sqrt[i]{n}\rfloor-1)$$ 直接计算即是 $\Theta(k\log n)$，可以轻松通过，需要注意精度问题 .