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)，可以轻松通过，需要注意精度问题 .