欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

杜教筛入门

程序员文章站 2022-04-14 21:55:44
Orz OO0OOO00O0OOO0O00OOO0OO 前置知识 狄利克雷卷积 杜教筛 套路 杜教筛是用来求一类积性函数的前缀和 它通过各种转化,最终利用数论分块的思想来降低复杂度 假设我们现在要求$S(n) = \sum_{i = 1}^n f(i)$,$f(i)$为积性函数,$n \leqsla ......

Orz  

前置知识

杜教筛

套路

杜教筛是用来求一类积性函数的前缀和

它通过各种转化,最终利用数论分块的思想来降低复杂度

假设我们现在要求$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。

如果需要真·杜教筛题目的话可以去看糖教的博客

https://blog.csdn.net/skywalkert/article/details/50500009

参考资料