【学习小记】狄利克雷卷积+杜教筛

Preface

这东西分明就是玄学暴力
用来求简单的数论函数的前缀和，像$φ,\mu$这类的东西

当然，约数和，约数个数之类的也是可以的

Text

数论函数是指定义域是整数，陪域是复数的函数

Dirichlet 卷积

定义两个数论函数$f,g$
它们的狄利克雷卷积表示$f*g$，设卷起来得到的新函数是$h$

$$h(i)=\sum\limits_{d|i}f(i)g({i\over d})$$
明显$h$也是一个数论函数

显然它满足交换，结合律，对加法满足分配律

有常见的一些数论函数
$1(i)=1，n(i)=n$（常函数）
$e(1)=1,e(n)=0(n>1)$（单位元）
$id(i)=i$
$id_k(i)=i^k$
$\mu(i)$（莫比乌斯函数，不解释）
$φ(i)$（欧拉函数，不解释）
约数个数，设为$d(i)=\sum\limits_{d|i} 1$
约数和，设为$\sigma(i)=\sum\limits_{d|i}d$

显然有以下常见的卷积形式

任意函数卷积单位元仍为它本身

• $d=1*1$

• $\sigma=id*1$

因为$e(n)=\sum\limits_{d|n}\mu(d)$
所以

• $e=1*\mu$

因为$φ(n)=\sum\limits_{d|n}\mu(d){n\over d}$
所以

• $φ=\mu*id$

因为$n=\sum\limits_{d|n}φ(d)$
所以

• $id=φ*1$

杜教筛

考虑如何求$\mu$的前缀和

比如说$10^{10}$？
线筛会T

设$S(n)=\sum\limits_{i=1}^{n}\mu(i)$
确定一个合适的数论函数$g$

$$\sum\limits_{i=1}^{n}(g*\mu)(i)=\sum\limits_{i=1}^{n}\sum\limits_{d|i}\mu({i\over d})g(d)$$
交换主体
$$=\sum\limits_{d=1}^{n}\sum\limits_{d|i}\mu({i\over d})g(d)$$
$$=\sum\limits_{d=1}^{n}g(d)\sum\limits_{i=1}^{\lfloor {n\over d}\rfloor}\mu(i)$$
$$=\sum\limits_{d=1}^{n}g(d)S({\lfloor {n\over d}\rfloor})$$

那么$g(1)S(n)=\sum\limits_{i=1}^{n}(g*\mu)(i)-\sum\limits_{d=2}^{n}g(d)S({\lfloor {n\over d}\rfloor})$

要使$g$和$g*\mu$尽量容易求，可以想到$g$用$1$函数是比较合适的，即$g(i)=1$

因为$1*\mu=e$
原式化为

$$S(n)=1-\sum\limits_{d=2}^{n}S({\lfloor {n\over d}\rfloor})$$

可以用线筛预处理前$\sqrt(n)$或者$n^{2\over 3}$的$S$，后面减的部分分块处理，递归下去，再哈希或者什么东西把算过的S记忆化一下

复杂度取决于预处理的多少

实验和理论都证明，预处理前$n^{2\over 3}$个S，总复杂度最优，为$O(n^{2\over 3})$

据说证明要用积分？然而我并不会。。。

对于求欧拉函数的前缀和，方法也是一样的，$g$仍取$1$，只不过$g*φ=id$
前面的1改成$n(n+1)/2$