版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
Powerful number 筛是一种能在最佳 $O(\sqrt n)$ 的时间下求一类积性函数前缀和的方法
<!-- more -->
{% note info no-icon %}
<a id="def-1-1">定义 - 1-1</a> Powerful number
令 $n\in\mathbb{Z}$ 的唯一分解式为 $n=\prod_{i=1}^{\omega(n)}p_i^{\alpha_i}$, 若 $\forall i\in[1,\omega(n)]_{\mathbb{N}},~\alpha_i>1$, 则称 $n$ 为 Powerful number
{% endnote %}
Powerful number 有如下性质
{% note success no-icon %}
<a id="th-1-1">定理 - 1-1</a> $n$ 为 Powerful number $\iff~\exists a,b\in\mathbb{Z}, n=a^2b^3$
<details open> <summary><font color='orange'>Proof</font></summary>
令 $P_n:={(p_i,\alpha_i):p_i\in\text{Prime}^+,~p_i^{\alpha_i}\mid n,~p_i^{\alpha_i+1}\nmid n}$
$\implies$:
令
则
$$ P_n=P_1'\cup P_2',~P_1'\cap P_2'=\varnothing $$
令
则
$$ n=\prod_{i=1}^{\omega(n)}p_i^{\alpha_i}=a^2b^3 $$
$\impliedby$:
$$ n=a^2b^3=\prod_{(p,\alpha)\in P_a}p^{2\alpha}\cdot\prod_{(p,\alpha)\in P_b}p^{3\alpha}=\prod_{(p,\alpha)\in P_n}p^\alpha $$
不难发现 $\forall(p,\alpha)\in P_n,\alpha>1$
</details>
{% endnote %}
{% note success no-icon %}
<a id="th-1-2">定理 - 1-2</a>
$$ |{m\in\mathbb{Z}_n:m~\text{is}~\text{powerful}~\text{number}}|=O(\sqrt{n}) $$
<details open> <summary><font color='orange'>Proof</font></summary>
$$ |{m\in\mathbb{Z}_n:m~\text{is}~\text{powerful}~\text{number}}|=O\left(\int_1^{\sqrt{n}}\sqrt[3]{\frac{n}{x^2}}\mathrm{d}x\right)=O(\sqrt{n}) $$
</details>
{% endnote %}
对积性函数 $f$, 我们要找到积性函数 $g$ 满足 $g(p)=f(p)$
令积性函数 $h=f*g^{-1}$
显然, $f(p)=h(p)g(1)+h(1)g(p)=h(p)+f(p)$, 故 $h(n)\ne 0\implies n$ 为 Powerful number
我们有
$$ \sum_{i=1}^nf(i)=\sum_{i=1}^n(h*g)(i)=\sum_{i=1}^nh(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(j) $$
所以只需枚举 $O(\sqrt{n})$ 个 Powerful number, 暴力求出对应的 $h$ 值, 并求 $g$ 的前缀和即可求出 $f$ 的前缀和
{% icodeweb blog lang:cpp powerful-num/main.cpp %}