Preface
这东西分明就是玄学暴力
用来求简单的数论函数的前缀和，像φ,μ这类的东西
当然，约数和，约数个数之类的也是可以的
Text
数论函数是指定义域是整数，陪域是复数的函数
Dirichlet 卷积
定义两个数论函数f,g
它们的狄利克雷卷积表示f∗g，设卷起来得到的新函数是h
h(i)=∑d|if(i)g(id)
明显h也是一个数论函数
显然它满足交换，结合律，对加法满足分配律
有常见的一些数论函数
1(i)=1，n(i)=n（常函数）
e(1)=1,e(n)=0(n>1) （单位元）
id(i)=i
idk(i)=ik
μ(i)（莫比乌斯函数，不解释）
φ(i)（欧拉函数，不解释）
约数个数，设为d(i)=∑d|i1
约数和，设为σ(i)=∑d|id
显然有以下常见的卷积形式
任意函数卷积单位元仍为它本身
- d=1∗1
- σ=id∗1
因为e(n)=∑d|nμ(d)
所以
- e=1∗μ
因为φ(n)=∑d|nμ(d)nd
所以
- φ=μ∗id
因为n=∑d|nφ(d)
所以
- id=φ∗1
杜教筛
考虑如何求μ的前缀和
比如说1010？
线筛会T
设S(n)=∑i=1nμ(i)
确定一个合适的数论函数g
∑i=1n(g∗μ)(i)=∑i=1n∑d|iμ(id)g(d)
交换主体
=∑d=1n∑d|iμ(id)g(d)
=∑d=1ng(d)∑i=1⌊nd⌋μ(i)
=∑d=1ng(d)S(⌊nd⌋)
那么g(1)S(n)=∑i=1n(g∗μ)(i)−∑d=2ng(d)S(⌊nd⌋)
要使g和g∗μ尽量容易求，可以想到g用1函数是比较合适的，即g(i)=1
因为1∗μ=e
原式化为
S(n)=1−∑d=2nS(⌊nd⌋)
可以用线筛预处理前(√n)或者n23的S，后面减的部分分块处理，递归下去，再哈希或者什么东西把算过的S记忆化一下
复杂度取决于预处理的多少
实验和理论都证明，预处理前n23个S，总复杂度最优，为O(n23)
据说证明要用积分？然而我并不会。。。
对于求欧拉函数的前缀和，方法也是一样的，g仍取1，只不过g∗φ=id
前面的1改成n(n+1)/2