Powerful Number 和特征函数

学了 $\rm Min\_25$ 筛，于是顺便学习了 $\rm Powerful\ Number$。
碰巧的是，看到了 $\rm Kewth$ 的这篇博客 。于是稍微总结一下所学。

Powerful Number 筛法

$\rm Powerful\ Number$ 是指每个质因子的次数都不小于 $2$ 的数。比如 $4,8,9,\cdots$ 。

现在有积性函数 $f(x)$ ，我们要求它的前缀和。
假设另有积性函数 $g(x)$ ，满足 $g(x)$ 和 $f(x)$ 在质数处的函数值相等。
设 $h=f*g^{-1}$ ，根据迪利克雷卷积的性质，$h$ 也是积性函数。
同时，对于质数 $p$ ，由于 $f(p)=g(p)h(1)+g(1)h(p)$ 且 $f(1)=h(1)=g(1)=1$ ，那么 $h(p)=0$ 。

因为 $h(p)=0$ 且 $h(x)$ 是积性函数，所以 $h(x)$ 只在 $\rm Powerful\ Number$ 处有值。

我们把要求和的式子展开：

$\begin{aligned} \sum_{i=1}^{n}f(i)&=\sum_{i=1}\sum_{d|i}h(i)g(\frac{i}{d})\\ &=\sum_{i=1}^{n}h(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(j) \end{aligned}$

我们爆搜所有的 $\rm Powerful\ Number$ ，并只在这些位置求 $g$ 的前缀和，就可以大幅优化求 $f$ 的前缀和的过程。事实上，$\rm Powerful\ Number$ 的数量是 $\mathcal{O}(\sqrt{n})$ 级别的，所以 $\rm Powerful\ Number$ 的复杂度优于 $\rm Min\_25$ 筛和杜教筛，可以跑 $10^{13}$ 的数据。

具体来说，如果求 $g$ 的前缀和可以做到 $\mathcal{O}(1)$ ，那么复杂度就是 $\mathcal{O}(\sqrt{n})$ 的；如果 $g$ 的前缀和可以做到 $\mathcal{O}(\sqrt{n})$ ，那么复杂度可以通过积分得到为 $\mathcal{O}(\sqrt{n}\log n)$ 。

但是 $\rm Powerful\ Number$ 的使用条件比较严苛。观察可以发现，我们要保证如下要求：

• 方便求出单个 $h(x)$ 的值。
• $g(x)$ 是积性函数，且方便求出 $g(x)$ 的前缀和。

那么我们在实践中如何更快地构造出满足条件的 $g(x)$ 呢？

构造卷积求前缀和

杜教筛是这一块广为流传的经典例子。
若已知 $g=f*h$ ，那么我们可以直接用杜教筛来求 $f(x)$ 的前缀和。

把上式换个方向，改为 $g=f*h$ ，那么 $f(x)$ 的前缀和可以用如下的方法求。

$\begin{aligned} \sum_{i=1}^{n}f(i)&=(\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}g(i)S_h(\lfloor\frac{n}{i}\rfloor)+h(i)S_g(\lfloor\frac{n}{i}\rfloor))-S_g(\lfloor\sqrt{n}\rfloor)S_h(\lfloor\sqrt{n}\rfloor) \end{aligned}$

特征函数

特征函数 $F(x)$ 是对于积性函数 $f(x)$ 而言的。满足 $F(x)$ 和 $f(x)$ 在质数处取值相等的函数 $F(x)$ 就可以称作 $f(x)$ 的特征函数。显然对于同一个 $f(x)$ ，会有不止一个 $F(x)$ ，但我们只考虑最简单的那个。

如果 $f(x)$ 在质数处 $p$ 的取值是一个关于 $p$ 的多项式，那么我们显然可以用若干个 $I_m(x)=x^{m}$ 线性相加得到 $F(x)$ 。

显然，两个积性函数作迪利克雷卷积，对应的特征函数线性相加。
那么如果两个积性函数在迪利克雷卷积下做除法，对应的特征函数线性相减。

我们重新考虑 $\rm Powerful\ Number$ 筛法的式子：

$h=f*g^{-1}$

可以发现，$h(x)$ 只在 $\rm Powerful\ Number$ 有值，等价于 $h(x)$ 的特征函数为 $H(x)=0$。

所以，如果我们构造一个特征函数与 $f(x)$ 相同的 $g(x)$ ，就可以满足 $h(x)$ 只在 $\rm Powerful\ Number$ 处有值。

当我们认为 $m$ 是常数时， $I_m(x)$ 是可以 $\mathcal{O}(1)$ 求前缀和的。所以，如果 $F(x)$ 可以拆成恰好两个形如 $x^k$ 的单项式之和时，假设为 $x^a + x^b$ ，那么我们可以构造 $g(x)=I_a*I_b$ ，此时，根据「构造卷积求前缀和」一节的结论，我们可以在 $\mathcal{O}(\sqrt{n})$的时间求出 $g(x)$ 的前缀和。

同样，若 $f(x)$ 可以拆成恰好两个形如 $x^k$ 的单项式之差时，我们也可以通过杜教筛在 $\mathcal{O}(n^{\frac{2}{3}})$ 求 $g(x)$ 的前缀和。

所以，若 $F(x)$ 可以写成特定的形式，通过特征函数，我们可以同时解决 $g(x)$ 的两个限制。

对于求单个 $h(x)$ 的值，博主本人也没有什么好办法。但是在实践中，我们可以利用 $h(x)$ 是积性函数的性质，手玩/打表找出 $h(p^k)$ 的值，并据此找规律。

实在不行的话就转 $\rm \sout{Min\_25}$ 筛吧

例题

Description

给定 $n$ ，求下面这个函数的前缀和：

$f(i)= \begin{cases} 1\ \ \ \ \ \ \ \ \ \ i=1\\ 2^{\Omega(i)} \ \ \ \ \ i>1 \end{cases}$

其中 $\Omega(x)$ 表示最大的 $k$ 使得 $x$ 能写成 $k$ 个大于 $1$ 的整数（可以相同）的乘积。
$n\leq 10^{13}$ 。