如果数 \(x\) 满足 \(x\) 所有的质因数的指数都至少为 \(2\)，则 \(x\in PN\)。那么显然，所有的 \(x\in PN\) 都可以被表示成 \(a^2b^3\)，这是因为所有除了 \(1\) 的正整数都可以被表示成 \(2a+3b\) 的形式。所以 \(n\) 以内的 \(\rm Powerful Number\) 数量可以估为：
现在考虑要求一个积性函数 \(f(i)\) 的前缀和，我们构造一个积性函数 \(g(i)\)，满足 \(g\) 和 \(h\) 在质数处的取值相同且 \(g\) 易于计算前缀和，接下来我们尝试构造积性函数 \(h\) 使得有 \(f=g*h\)，这里的 \(*\) 是狄利克雷卷积。
我们可以暴力求出 \(h\) 所有质数幂处的取值，只需利用：
可以在 \(k^2\) 的时间复杂度内求出 \(h(p^0),h(p^1),h(p^2),\cdots h(p^k)\) 处的取值。
考虑这样构造出来的 \(h\) 一定是满足要求，否则，设有 \(f'=g*h\)，考虑 \(f'\) 和 \(f\) 在质数幂上的取值相同，而 \(f'\) 是积性函数，所以有 \(f'=f\)。
令 \(k=1\)，我们有：
这说明 \(h(p)=0\)，也就是说，\(h\) 只在 \(\rm Powerful Number\) 数的位置才有值，除了 \(1\)。
考虑 \(f(x)\) 的前缀和：
于是我们可以只枚举 \(O(\sqrt{n})\) 个 \(\rm Powerful Number\) 即可，复杂度为 \(O(\sqrt n)\)。
如何求出所有 \(\rm PowerfulNnumber\)？只需要预处理所有 \(\sqrt{ n}\) 以内的质数然后暴力搜索它们的质数即可。