Oql's Blog

发表于 分类于

Powerful Number

定义

一个数 $n$ 满足 $\forall p((p\in \mathbb{P} \wedge p|n )\rightarrow p^2|n )$，则称 $n$ 为Powerful Number（简称PN）。

显然，所有的PN都可表示为 $a^2b^3$ （其中 $(a,b)=1$ ）的形式。

个数

  • $n$ 以内的PN数是 $O(\sqrt{n})$ 个的。

证明：$n$ 以内PN数的个数 $\le \int_{1}^{\sqrt{n}}(\frac{n}{x^2})^{1/3}\text{ d}x=O(\sqrt{n})$。

求出 $n$ 以内的PN数可以暴力搜索质因数。

PN筛

通过 Powerful Number 可以求出一系列积性函数的前缀和。

假设我们要求 $\sum_{i=1}^nf(i)$，构造两个函数 $g,h$ 使得：

  • $g$ 是积性函数。且 $g$ 的前缀和 $S_g(n)$ 容易求出。
  • $\forall p\in \mathbb{P},g(p)=f(p)$。
  • $f=g * h$。

那么，将原式变一变：

$$
\sum_{i=1}^n f(i) \ =\sum_ {i=1}^n\sum_{d|i }h(d) g ( \frac{i}{d} ) \ =\sum_{i=1}^n h(i)\sum_{j=1} ^ { \frac{n}{i} }g(j) \ =\sum_{i=1}^n h(i)S_g(\left \lfloor \frac{n}{i} \right \rfloor)
$$

观察一下 $h$ 的取值：可以发现 $f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)$，又因为有 $g(p)=f(p)$，因此 $h(p)=0$。

显然 $h$ 是个积性函数，那么由积性函数的定义，对于 $h$ 的所有非 PN 数下标的取值均为 $0$。

我们只需快速求出所有 PN 数下标的 $h$ ，就可以了。

只需要求出 $h(p^k)$ 就可以了。这个可以通过推式子或者递推等解决。

时间复杂度一般是 $O(\sqrt{n})$ 的。