版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: 笔记 - Powerful number 与 Powerful number 筛 categories:
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^{\alphai}$, 若 $\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_1'=\{(p_i,\alpha_i)\in P_n:2\mid\alpha_i\}$ - $P_2'=\{(p_i,\alpha_i)\in P_n:2\nmid\alpha_i\}$ 则 $$ P_n=P_1'\cup P_2',~P_1'\cap P_2'=\varnothing $$ 令 - $$ a=\prod_{(p,\alpha)\in P_1'}p^\frac{\alpha}{2}\prod_{(p,\alpha)\in P_2'}p^\frac{\alpha-3}{2} $$ - $$ b=\prod_{(p,\alpha)\in P_2'}p $$ 则 $$ 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$ 的前缀和