杜教筛入门
2018-07-22 05:46:32来源:博客园 阅读 ()
Orz OO0OOO00O0OOO0O00OOO0OO
前置知识
狄利克雷卷积
杜教筛
套路
杜教筛是用来求一类积性函数的前缀和
它通过各种转化,最终利用数论分块的思想来降低复杂度
假设我们现在要求$S(n) = \sum_{i = 1}^n f(i)$,$f(i)$为积性函数,$n \leqslant 10^{12}$
直接求肯定是不好求的,不过现在假设有另一个积性函数$g$
我们来求它们狄利克雷卷积的前缀和
$$(g * f) = \sum_{i = 1}^n \sum_{d \mid i} g(d) f(\frac{i}{d})$$
$$= \sum_{d = 1}^n g(d) \sum_{d|i} f(\frac{i}{d})$$
$$= \sum_{d = 1}^n g(d) \sum_{i = 1}^{\frac{n}{d}}f(i)$$
$$= \sum_{d = 1}^n g(d) S(\frac{n}{d})$$
然后就化不动了,不过我们发现我们化出了$\frac{n}{d}$!excited
但是$S(n)$怎么求呢?
容斥一下
$$g(1)S(n) = \sum_{d = 1}^n g(d)S(\frac{n}{d}) - \sum_{d = 2}^n g(d)S(\frac{n}{d})$$
前半部分是狄利克雷卷积的前缀和的形式
后半部分可以数论分块。这样看起来就好搞多了
现在我们的问题是,如何选择$g$才能使得上面这个式子好算
这个就要因情况而定了
下面煮几个典型栗子
$\mu$函数
定理:$\sum_{d \mid n} \mu(d) = [n = 1]$
那么我们如果选择$g = e$,$e$为原函数,$e = [n = 1]$
$g$与$\mu$的卷积的前缀和肯定为$1$
上面的式子变为
$S(n) = 1 - \sum_{d = 2}^n S(\frac{n}{i})$
后半部分直接数论分块就好
$\varphi$函数
定理:$\sum_{d \mid n}\varphi(d) = n$
我们的$g$还是选$e$做卷积
我们要求得式子变为
$$S(n) = \frac{n * (n + 1)}{2} - \sum_{d = 2}^n S(\frac{n}{i})$$
前半部分$O(1)$算,后半部分数论分块
题目
目前没有做多少题目,而且我的杜教筛是分两波学的,所以码风差异可能比较大qwq。
洛谷P4213 Sum
BZOJ4805
BZOJ4916
如果需要真·杜教筛题目的话可以去看糖教的博客
https://blog.csdn.net/skywalkert/article/details/50500009
参考资料
杜教筛——省选前的学习1
我也不知道什么是"莫比乌斯反演"和"杜教筛"
浅谈一类积性函数的前缀和
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Window中的shellcode编写框架(入门篇) 2020-03-31
- 蓝桥杯练习(入门一) 2020-03-23
- c语言该怎么入门?C语言入门教程(非常详细) 2020-02-17
- 习题2-6:排列 2019-12-30
- C++入门到理解阶段二基础篇(9)——C++结构体 2019-11-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash