Powerful Number 学习笔记

Powerful Number的定义是所有质因子的指数都大于$1$数，简单积一下发现只有$O(\sqrt{n})$个。下面是它在求积性函数前缀和中的应用。 设我们要求积性函数$f(n)$的前缀和$F(n)$，考虑我们能找到一个性质更好（前缀和易求）的积性函数$g(n)$，满足对于质数$p$有$g(p)=f(p)$。我们考虑$f/g=h$，由于$f,g$都是积性函数，所以有$f(1)=g(1)=1$，又因为$f(p)=g(p)\times h(1)+g(1)\times h(p)$，所以有$h(1)=1,h(p)=0$。又因为$h$也是积性函数，所以$h$只会在Powerful Number处有值，其余处都是$0$。（假设Powerful Number的集合为$\mathbb{P}\mathbb{N}$）于是有， $$F(n)=\sum _{xy\le n}g(x)h(y)=\sum _{y\in \mathbb{P}\mathbb{N}}h(y)G(\lfloor \frac{n}{y}\rfloor )$$ 于是在$h$的单点值好求，$g$的前缀和好求的情况下就可以很快地求出$F$了。