Powerful_Number

Powerful Number 筛类似于杜教筛，可以拿来求一些积性函数的前缀和。

要求存在数论函数 $g$ 满足：

• $g$ 是积性函数。
• $g$ 易求前缀和。
• 对于 $p \in \mathcal{ P }$，有 $g(p) = f (p )$。

现在需要求 $S _ f ( n ) = \sum _ { i = 1 } ^ { n } f ( i )$。

定义 PN：对于 $ n \in \mathbb{ N } _ +$，记 $n$ 的质因数分解为 $ n = \prod _ { i = 1 } ^ { k } p _ i ^ { c _ i }$，则 $n$ 是 PN 当且仅当 $\forall 1 \le i \le m , c _ i > 1$。

性质一：所有 PN 均能被表示为 $a ^ 2 b ^ 3$ 的形式。

性质二：$n$ 以内的 PN 至多有 $O(\sqrt{n})$ 个。

证明：先考虑枚举 $a$，再考虑满足条件的 $b$ 的个数：

$$\int _ { 1 } ^ { \sqrt{n} } \sqrt [ 3 ] { \dfrac { n } { x ^ 2 } } \, \delta x = O ( \sqrt { n } )$$

$\square$

至于如何求出 $n$ 以内的 PN？DFS，干就完了。

现引入 PN 筛的方法。

首先，构造 $g$，记 $S _ g ( n ) = \sum _ { i = 1 } ^ { n } g ( i )$，$h = f \ast g ^ { - 1 }$。

对于 $p \in \mathcal{ P }$，有：

$$ f ( p ) = h ( 1 ) g ( p ) + h ( p ) g ( 1 ) = h ( p ) + g ( p )$$

所以 $h ( p ) = 0 $，于是我们根据 $h$ 是积性函数可以推知对于非 PN 数 $n$ 有 $h ( n ) = 0 $。

现根据 $f = g \ast h$，有：

$$
\begin{aligned}
S _ f ( n ) = & \sum _ { i = 1 } ^ { n } f ( i )
\\
= & \sum _ { i = 1 } ^ { n } \sum _ { d \mid i } h ( d ) g \left( \dfrac { i } { d } \right)
\\
= & \sum _ { d = 1 } h ( d ) \sum _ { i = 1 } ^ { \lfloor n / d \rfloor } g ( i )
\\
= & \sum _ { d = 1 } h ( d ) S _ g \left( \left\lfloor \dfrac { n } { d } \right\rfloor \right)
\\
= & \sum _ { d \in \mathrm{PN} } h( d ) S _ g \left( \left\lfloor \dfrac { n } { d } \right\rfloor \right)
\end{aligned}
$$

现在需要做的事就是两件：

• $O ( \sqrt{n} )$ 找到 PN。
• 快速计算 $h$。

关于计算 $h( p ^ c )$，有两种方法：

• 直接推出 $h ( p ^ c )$ 的公式。
• 由 $f \ast g = h$ 得到 $ h (p ^ c ) = f ( p ^ c ) - \sum _ { i = 1 } ^ { c } g ( p ^ c ) h ( p ^ { c - i })$。

时间复杂度 $O( \sqrt {n} \log n)$，空间复杂度 $O( \sqrt {n} )$。

如果求 $g$ 的前缀和需要杜教筛，则主要瓶颈在这个 $O(n ^ { 2 / 3 })$。

现在尝试用这个来把 Min-25 的模板干掉。

例题：P5325 【模板】Min_25筛