如果数 $x$ 满足 $x$ 所有的质因数的指数都至少为 $2$，则 $x\in PN$。那么显然，所有的 $x\in PN$ 都可以被表示成 $a^2b^3$，这是因为所有除了 $1$ 的正整数都可以被表示成 $2a+3b$ 的形式。所以 $n$ 以内的 $\rm Powerful Number$ 数量可以估为：
$$
\int _1^{\sqrt{n}} \sqrt[3]{\frac{n}{x^2}}dx=O(\sqrt{n})
$$
现在考虑要求一个积性函数 $f(i)$ 的前缀和，我们构造一个积性函数 $g(i)$，满足 $g$ 和 $h$ 在质数处的取值相同且 $g$ 易于计算前缀和，接下来我们尝试构造积性函数 $h$ 使得有 $f=gh$，这里的 $$ 是狄利克雷卷积。
我们可以暴力求出 $h$ 所有质数幂处的取值，只需利用：
$$
f(p^k)=\sum\limits_{i=0}^k g(p^i)h(p^{k-i})
$$
可以在 $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$，我们有：
$$
f(p)=g(p)h(1)+g(1)h(p)=g(p)
$$
这说明 $h(p)=0$，也就是说，$h$ 只在 $\rm Powerful Number$ 数的位置才有值，除了 $1$。
考虑 $f(x)$ 的前缀和：
$$
\sum\limits_{i=1}^nf(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}h(d)g(\frac{i}{d})=\sum\limits_{d=1}^nh(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}g(i)
$$
于是我们可以只枚举 $O(\sqrt{n})$ 个 $\rm Powerful Number$ 即可，复杂度为 $O(\sqrt n)$。
如何求出所有 $\rm PowerfulNnumber$？只需要预处理所有 $\sqrt{ n}$ 以内的质数然后暴力搜索它们的质数即可。