Powerful Number 筛

题目：

Powerful Number 筛也是一种筛，它是 $O(\sqrt n)$ 的。应用时必须满足

• 它是积性函数

• 这个东西在质数处取值的函数可以快速计算前缀和。例如此题，显然有 $f(p) = 1$ 。

首先 Powerful Number 的定义，是所有质因子次数都 $\ge 2$ 的数。这种数的个数是 $O(\sqrt n)$ 级别的。因为显然，每个这样的数都可以被表示成 $a^2b^3$ ，所以寻找这种数的时候可以暴力枚举这里的 $a,b$ ，复杂度是 $\sum_{i=1}^{\sqrt n} (\frac n {i^2})^{\frac 1 3}$ ，这个东西积分一下会发现是 $O(\sqrt n)$ 的。

现在，假设我们已经有了一个函数 $f'(p) = f(p),p \in \text{prime}$ 。现在我们想通过这个东西容斥出 $f$ 。具体来说，我们来尝试找到一个容斥系数 $h$ ，满足

$f(x) = \sum_{d|x} f'(d)h(\frac d x)\\ h = f / f'$

显然我们有

$h(1) = 1\\ h(1)f'(p) + h(p)f'(1) = f(p)\\ f'(p) + h(p)f'(1) = f(p)$

因此我们有 $h(p) = 0$ 。所以 $h$ 仅在 Powerful Number 处有值！

因此有

$\begin{aligned} &\sum_{i=1}^n f(i)\\ =&\sum_{i=1}^n \sum_{pq = i} h(p)f'(q)\\ =& \sum_{pq \le n} h(p)f'(q)\\ =& \sum_{p} h(p) \sum_{q \le n/p} f'(q) \end{aligned}$

后面那个东西的前缀和事可以求的，而前面这个东西仅在 Powerful Number 处取值。