UOJ Logo negiizhao的博客

博客

OI中(?)常用数论函数求和法的大致描述、zzt求和法的简化版

2021-07-11 06:32:00 By negiizhao

如果还不会,或许也可以先从wc2018的原始课件或者 zzt blog(里面有一些小bug) 看一点基础知识.


从最基础的知识开始介绍吧,首先是 Dirichlet 双曲线法,对于数论函数 $f, g, h : \mathbb Z^+ \to R,f=g*h$,其中 $*$ 为 Dirichlet 卷积,$R$ 为交换环(并且有时假设,对于整数到 $R$ 的同态,较小的正整数的像可逆),那么有 $$ \sum _{n\leq x}f(n)=\sum _{n\leq x}\sum _{ab=n}g(a)h(b)=\sum _{a\leq {\sqrt {x}}}\sum _{b\leq {\frac {x}{a}}}g(a)h(b)+\sum _{b\leq {\sqrt {x}}}\sum _{a\leq {\frac {x}{b}}}g(a)h(b)-\sum _{a\leq {\sqrt {x}}}\sum _{b\leq {\sqrt {x}}}g(a)h(b) $$

从图像上理解,相当于是平面直角坐标系第一象限有一条双曲线 $\displaystyle y=\frac{n}{x}$ 也就是 $xy=n$,我们要对其下方(包括线上)的所有整点对 $(x, y)$,求 $g(x)h(y)$ 的和.我们对 $x \leq \sqrt n$ 的部分、$y \leq \sqrt n$ 的部分分别求和,再减去两者的公共部分.

james2.png

也许会有人更熟悉“整除分块”的做法,它和上式只相差一个 Abel 变换,我想这个做法或许会方便操作,常数更小一些,不过无论如何二者能力是差不多的.

无论是用哪个式子,我们都需要知道 $g$ 和 $h$ 在一些位置上的前缀和(这里当然认为我们对 $g$ 和 $h$ 的单点值并没有更多了解).这个位置的集合是我们非常熟悉的整除集合 $\displaystyle D_n=\left\{\left\lfloor\frac nm \right\rfloor \;\middle|\; m\in\mathbb Z^+ \right\}=\left\{0, 1, 2, \dots, \left\lfloor\sqrt n\right\rfloor-1, \left\lfloor\sqrt n\right\rfloor, \left\lfloor\frac n {\left\lfloor\sqrt n\right\rfloor}\right\rfloor, \left\lfloor\frac n {\left\lfloor\sqrt n\right\rfloor-1}\right\rfloor, \dots, \left\lfloor\frac n 2\right\rfloor, n\right\}$,这个集合的一些性质就不赘述了,可以参考 zzt blog.

可以看出来,这些位置的前缀和值是很重要的.我们记 $S_{n, f} : D_n \to R$ 表示 $f$ 在整除集合位置的前缀和函数,那么上文说明我们可以由 $S_{n, g}$ 和 $S_{n, h}$ 得到 $g*h$ 的前 $n$ 项和.我们对此并不满意:也许 $g*h$ 只是计算过程的一小步,我们希望可以得到 $S_{n, g*h}$.而这也不难做到,因为整除位置的整除集合是整除集合的子集,只需要直接对每个位置求一遍即可.经过计算容易得出这一过程的时间为 $\Theta(n^{3/4})$.

我们仍然不满意:这一过程还是稍微慢了一点.考虑对小于 $S$ 的位置暴力计算 Dirichlet 卷积求解,这样时间为 $O\left(S\log S+\sqrt n\sqrt{\frac nS}\right)$,取 $S=\Theta\left(\left(\frac{n}{\log n}\right)^{2/3}\right)$ 时为 $\Theta(n^{2/3}\log^{1/3} n)$.若数论函数为积性函数,可以通过记录 $S$ 以内函数的完整信息,增大空间开销使计算卷积的时间降为 $\Theta(S)$,此时取 $S=\Theta(n^{2/3})$ 时总时间为 $\Theta(n^{2/3})$.此外注意到对于 $f=g*h$,这种方法亦可用于已知 $S_{n, f}$ 和 $S_{n, g}$ 反推 $S_{n, h}$,由于一些历史原因,这种用法常常被称为“杜教筛”.

在一些特殊情况下(对,我的意思是下文会用到),两个函数的非零项密度为 $O(\log^{-1} n)$,此时时间为 $O\left(S\log S\log^{-2} n+\sqrt n\sqrt{\frac nS}\log^{-1} n\right)$,取 $S=\Theta(n^{2/3})$ 时总时间为 $\Theta(n^{2/3}\log^{-1}n)$.


现在我们考虑适用于一类积性函数的求和法,它要求函数在素数处的取值是关于素数的常数次多项式.

考虑积性函数的 Dirichlet 生成函数,作为积性函数,无非是意味着 $\displaystyle\mathrm{DGF}(f):=\sum_{n=1}^\infty f(n)n^{-s}=\prod_p\left(1+\sum_{k=1}^\infty f(p^k)(p^k)^{-s}\right)=:\prod_p\mathrm{DGF}(f_p)$.

可以花费 $O(\sqrt n\log_pn)$ 时间由 $S_{n, g}$ 得出 $S_{n, g*f_p}$ 或 $S_{n, g*f_p^{-1}}$.对于大于 $\sqrt n$ 的素数 $p$,我们无须关心其幂次位置的取值,于是考虑先求出关于这部分素数的多项式的前缀和.对多项式中不同的幂次 $k$,从 $id_k(n)=n^k$ 的前缀和 $S_{n, id_k}$ 开始,除去所有小于等于 $\sqrt n$ 的素数 $p$ 的贡献,再将其按照多项式进行组合(此时得到了 $\displaystyle\prod_{p>\sqrt n}\mathrm{DGF}(f_p)$ 对应的函数的前缀和),最后直接乘上其他素数的贡献即可.去除一些无用计算后,可以得到一个 $\Theta(n^{3/4}\log^{-1}n)$ 的算法,常被称为“洲阁筛”.其另有一个较小数据范围内速度较快的搜索变种,常被称为“min_25筛”.


此类方法还是不够令人满意.考虑按素数大小把这些因子分为 3 部分分别处理,即 $\displaystyle\mathrm{DGF}(f)=\left(\prod_{p\le n^{1/6}}\mathrm{DGF}(f_p)\right)\left(\prod_{n^{1/6}< p\le n^{1/2}}\mathrm{DGF}(f_p)\right)\left(\prod_{n^{1/2}< p}\mathrm{DGF}(f_p)\right)$.

先求出第二部分,注意到 $\displaystyle \prod_{n^{1/\alpha}< p\le n^{1/2}}\mathrm{DGF}(f_p)=\exp\sum_{n^{1/\alpha}< p\le n^{1/2}}\log\mathrm{DGF}(f_p)$,而 $\exp$ 内部式子最低项 $6$ 次方已超出 $n$,对答案无影响.于是只需要计算其 2、3、4、5 次方.注意到涉及的函数的非零项密度皆为 $O(\log^{-1} n)$(证明可参考zzt blog),所以计算这部分总时间为 $\Theta(n^{2/3}\log^{-1}n)$.

对于第一部分,考虑直接逐项乘到答案中,时间为 $\displaystyle \sum_{p\le n^{1/6}}O(\sqrt n\log_pn)=\int_1^{n^{1/6}}O(\sqrt n\log_pn)\log^{-1}p\,\mathrm{d}p=O(n^{2/3}\log^{-1}n)$.

对于第三部分,类似之前的做法,分解为从 $S_{n, id_k}$ 中去除小素数贡献的问题.可以用前面的方法直接算出小素数的前缀和函数,由于这部分的前缀和函数 $\sqrt n$ 以内几乎全为 0,所以用除法计算出来,再乘到答案上是很容易做到的,这部分时间也为 $\Theta(n^{2/3}\log^{-1}n)$.

以上算法大概就是简化后的zzt求和法了()可以看出,这种求和法所需时间实际上只和做此类乘法的时间有关.

暂时还没有进一步研究,也没考虑怎么卡常,因为↓

写了一份代码,虽然过了模板题,但好像还有些没弄明白的bug(我家乘法不结合.png),其中282行~294行是与题目本身有关的内容,此外都是模板,感觉代码量还是有点大的.

现在修好了,拆解了一些过程,现在287行~299行是与题目本身有关的内容.

修了一下,现在303行~315行是与题目本身有关的内容.

upd:仿佛整出来了个 $O(n^{2/3}\log^{-4/3}n)$ 甚至 $O(n^{2/3}\log^{-2}n)$ 的做法,还有更快的算 $\pi(n)$ 的做法,甚至让我想写点东西发出去,暂时就不公开了(x

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。