0%

min25 筛和 Powerful Number 筛

两种求积性函数前缀和的方法。

Powerful Number 筛

要求

  • 积性

  • 有一个和它在质数处取值相等的简单函数

做法

Powerful Number 是指其每一个质因数的次数都大于等于 2 的数。可以证明其数量是 $O(\sqrt n)$ 的。

假设我们要求 $F$ 的前缀和,设计积性函数 $G$,使得对于质数 $p$ 有 $G(p)=F(p)$,设 $H$ 使 $F=G*H$,于是就有 $H(p)=0$,又因为 $H$ 显然也积性,从而 $H$ 只在 Powerful Number 处取非 0 值。

然后考虑一个和杜教筛一样的柿子:

可以取巧妙的 $G$ 使得它容易杜教筛。$H(p^k)$ 一般也比较容易分析。接下来直接爆搜出所有的 Powerful Number 和它们的函数值即可。

非常好写,而且如果 $G$ 的前缀和很容易求的话可以 $O(\sqrt n)$。

Min25 筛

要求

  • 积性

  • 在质数的幂处的取值是项数较少的多项式

做法

思路借鉴了模板题第二篇题解,努力讲的清楚了一些,我尽力了……

设要求的是 $\sum_{i=1}^n f(i)$。先按质数和合数分类,合数再按其最小质因子分类,注意合数 $n$ 的最小质因子小于等于 $\sqrt n$:

兄啊,这不是每一项都不能算吗(恼)

我们先考虑一下 $f$ 在质数处的值之和。

质数处的值

我们搞出一个函数 $f’(x)$,这个函数完全积性,在质数处取值和 $f(x)$ 一样。考虑一个 DP,设

其中 $p_j$ 是第 $j$ 个质数。

当 $j\leftarrow j+1$,会有一些 $i$ 变得不满足条件,也就是那些最小质因子 $=p_j$ 的合数。

如果提出一个 $p_j$(因为完全积性所以随便提),那么对它们的要求就只有:没有小于 $p_j$ 的因子,而且不是小于 $p_j$ 的质数。也就是 $g(\frac{n}{p_j},j-1)-g(p_{j-1},j-1)$。

所以

那个 $g(p_{j-1},j-1))$ 就是小于 $p_j$ 的质数之 $f’$ 和。线性筛的同时处理。

于是发现用到的 $n$ 只有 $O(\sqrt n)$ 种。(可以不用 map 存储,大意就是对 $x\le \sqrt n$ 直接存到第一个桶,否则映射到第二个桶的 $\frac{N}{x}$ 处)

总结一下就是靠一个 DP 一步步把非质数值给清洗掉。类似埃氏筛?

设 $m$ 是 $p_m^2\le n$ 的最大 $m$。则 $g(n,m)$ 就是所有质数的函数值和,不过我们不打算直接使用。

整个柿子

故技重施,设 $S(n,j)$ 是最小质因数大于 $p_j$ 的 $f(i)$ 和,则有

复杂度

考虑对 $g$ 的 DP。用到的一个 $n=\lfloor\dfrac{N}{x}\rfloor$ 会枚举小于等于 $\sqrt n$ 的所有质数,我们知道小于 $n$ 的质数是 $O(\dfrac{n}{\ln n})$ 的,于是积一下可以知道是 $O(\dfrac{n^{3/4}}{\ln n})$。

对 $S$ 的 DP 可以证明是 $O(n^{1-\epsilon})$ 的。

例题