不会做拉插来的。
注意到肯定是枚举最大平方因子 \(i\)，对于 \(\le \frac{n}{i}\) 的所有数 \(x\)，如果其没有平方因子我们要加上 \(x^k\)，否则不加。需要一个合理的手段判断 \(x\) 是否有平方因子，由于涉及平方项，不难想到莫比乌斯反演，先对 \(x\) 的平方因子容斥：
\[[x \ \text{is ok}] = \sum_{j^2 | x} d(j)
\]
其中 \(d(j)\) 是我们的容斥系数，通过一些惊人的手段可以发现 \(d(j) = \mu(j)\)，这是因为：
\[[j = 1] = [2^j \bmod 2 = 1]
\]
具体原因可以细品，反正猜猜就猜出来是一个和 \(\mu\) 有关的式子。
然后同时枚举 \(i, j\)，此时的问题就变成了自然数幂和，使用根号分治加拉插即可做到能过的复杂度。