Powerful number

$\text{Powerful number}$

定义

$\text{PN}$表示$\text{Powerful number}$的集合，记$n$的质因数分解为${\prod }_{i=1}^m{p}_i^{c_i}$，$n\in \text{PN}$当且仅当$\forall i,c_i\ge 2$

性质1 $n\in \text{PN}$可以被表示为$a^2{b}^3$的形式

性质2 $n\in \text{PN}$且$n\le m$，这样的数个数为$O(\sqrt{m})$级别

证明：$${\int }_1^n\sqrt[3]{\frac{n}{x^2}}=O(\sqrt{n})$$

$\text{PN}$筛

求${\sum }_{i=1}^{n}f(i)$，$f(i)$是个积性函数

要求：

• 构造积性函数$g(i)$，使得$\forall p\in \mathbb{P},g(p)=f(p)$
• $g(i)$能够快速求前缀和

做法：

构造$f=g\ast h$，其中$\ast$表示狄利克雷卷积，$h$显然也为积性函数，故$h(1)=1$，由$f(p)=g(1)h(p)+g(p)h(1),f(p)=g(p),p\in \mathbb{P}$，可以得到$h(p)=0$，所以$h(i)>0$当且仅当$i\in \text{PN}$
$$\sum _{i=1}^{n}f(i)=\sum _{i=1}^n\sum _{j|i}h(j)g(\frac{i}{j})=\sum _{j=1}^{n}h(j)\sum _{i=1}^{\lfloor \frac{n}{j}\rfloor }g(i)$$
然后就可以用$dfs$枚举$\text{PN}$，顺便求出$h(i)$的值，然后通过快速计算$g$的前缀和就可以求出${\sum }_{i=1}^{n}f(i)$

分析

计算$h(i)$，可以直接看出通式或者用$h(p^c)=f(p^c)-{\sum }_{i=0}^{c-1}h(p^i)g(p^{c-i})$的递推式求，后者更加常见，$\le \sqrt{n}$的质数个数为$O(\frac{\sqrt{n}}{\log n})$，然后这样递推求$h$是${\log }^2$的，所以总复杂度是$O(\sqrt{n}\log n)$，这个递推式有时也可以根据$g$的一些特征优化到$\log$

例题

例1 hdu7186 Jo loves counting

求${\sum }_{i=1}^{n}f(i),i={\sum }_{j=1}^m{p}_j^{c_j},f(i)=\frac{i}{{\prod }_{j=1}^m{c}_j}$

solution

$g(i)=i$，求$h$时可以优化，所以最终的复杂度为$O(\sqrt{n})$

例2 P5325 【模板】Min_25筛

求${\sum }_{i=1}^{n}f(i),f(p^k)=p^k(p^k-1),p\in \mathbb{P}$

solution

$g(i)=i\phi (i)$，用杜教筛求$g$的前缀和，时间复杂度$O(n^{\frac{2}{3}})$