RainAir
My OI Blog
RainAir
杜教筛学习笔记

预备知识

杜教筛是一种能在比线性复杂度还优秀的复杂度中处理处积性函数的前缀和。

主要运用 Dircichlet 卷积来完成复杂度的化简。

定义

设 $ f(n) $ 为一个数论函数,$ S(n) = \Sigma_{i=1}^nf(i)$。

我们考虑再找到一个合适的数论函数 $g(i)$,使得

$$ \Sigma_{i=1}^n\Sigma_{d|i}f(d)g(\frac{i}{d}) = \Sigma_{i=1}^ng(i)S(\frac{n}{i}) \tag1$$

也就是

$$ g(1)S(n) = \Sigma_{i=1}^n(f*g)(i) – \Sigma_{i=2}^ng(i)S(\frac{n}{i}) \tag2$$

可以通过线性筛预处理前 $ O(n^{\frac{2}{3}}) $ 项,其他暴力递归算。复杂度为 $ O(n^{ \frac{2}{3}}) $。

例题

题目链接

题目描述

有 $ T $ 组询问,对于每组询问,给出一个数 $ n $,求 $$ \Sigma_{i=1}^n \mu(i) $$ 和 $$ \Sigma_{i=1}^n \phi(i) $$ 的值。

其中 $ n \leq 2^{31}-1,T \leq 10 $

解题报告

莫比乌斯函数 $ \mu $

$$ \Sigma_{i=1}^n\mu(i) \tag1$$

我们需要选取一个合适的函数,使得

$$ g(1)S(n) = \Sigma_{i=1}^n(f*g)(i) – \Sigma_{i=2}^ng(i)S(\frac{n}{i}) \tag2 $$

中 $ g $ 和 $ S $ 是容易快速处理的,这样就可以推出 $ f $。

显然,我们对于第一个式子选择常函数 $ f(x) = 1 $

$ (2) $ 式变形为:

$$ S(n)=\Sigma_{i=1}^n(\mu*1)(i) – \Sigma_{i=2}^n S(\lfloor\frac{n}{i}\rfloor) \tag3$$

注意性质 $ \mu * 1 = e $,整理得到

$$ S(n) = 1 – \Sigma_{i=2}^nS(\lfloor\frac{n}{i}\rfloor) \tag4$$

直接计算的复杂度为 $ O(n^{\frac{3}{4}}) $ ,但是可以考虑线性筛处理前 $ n^{\frac{2}{3}} $ 项,这样递推时间复杂度为:

$$ O(\int^{n^{\frac{1}{3}}}_0\sqrt{\frac{n}{x}}dx) = O(n^{\frac{2}{3}}) \tag1 $$

$ (1) $ 式结合线性筛部分,总复杂度为 $ O(n^{\frac{2}{3}}) $。

欧拉函数 $ \phi $

用和上题一样的方法,留给读者自己思考。

提示: 欧拉函数有性质 $ \phi * 1 = id $。

参考代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/96
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

杜教筛学习笔记
预备知识 杜教筛是一种能在比线性复杂度还优秀的复杂度中处理处积性函数的前缀和。 主要运用 Dircichlet 卷积来完成复杂度的化简。 定义 设 $ f(n) $ 为一个数论函数,$ S(n) = \Si…
扫描二维码继续阅读
2018-08-17
标签
近期评论