一个没啥用的东西，权当加深对数论函数和狄利克雷卷积的理解。
序列 { f 1 , f 2 , … } \{f_1,f_2,\dots\} {f1,f2,…} 的狄利克雷生成函数 DGF 定义为
f ( s ) = ∑ n = 1 ∞ f n n s f(s)=\sum_{n=1}^{\infin}\frac{f_n}{n^s} f(s)=n=1∑∞nsfn
这里不要求 f f f 是积性函数。
显然两个序列的狄利克雷卷积的 DGF 等于它们 DGF 的乘积。
为什么 n s n^s ns 要写在下面？
本质上写上面也没啥区别，但是在这之前有个叫黎曼的数学家整了个叫 Zeta 的函数（马上就会讲到），为了让收敛的形式好看一点就定义成了分数。后来大家就沿用了这一习惯。
本文中为了方便起见，可能会混用 n − s n^{-s} n−s 的写法。
黎曼 Zeta 函数定义为
ζ ( s ) = ∑ n = 1 ∞ 1 n s \zeta (s)=\sum_{n=1}^{\infin}\frac1 {n^s} ζ(s)=n=1∑∞ns1
对就是那个臭名昭著的猜想里面的那个函数。
不难看出 Zeta 函数是恒等函数 I ( n ) = 1 I(n)=1 I(n)=1 的 DGF，这和 OGF 的 1 1 − x \frac 1{1-x} 1−x1,EGF 的 e x e^x ex 有着同样的地位，是 DGF 理论的基石。
既然是狄利克雷卷积，我们希望这个能与积性函数的理论扯上关系。
以 Zeta 函数为例，我们把每个 n n n 质因数分解，然后考虑每个质数 p p p 的贡献，不难得到
ζ ( s ) = ∏ p ∈ p r i m e ∑ i = 0 ∞ 1 p i s = ∏ p ∈ p r i m e 1 1 − p − s \zeta(s)=\prod_{p\in prime}\sum_{i=0}^{\infin}\frac 1{p^{is}}\\=\prod_{p\in prime}\frac{1}{1-p^{-s}} ζ(s)=p∈prime∏i=0∑∞pis1=p∈prime∏1−p−s1
其他积性函数也可以用类似方法转成一个伪封闭形式。
∏ p ∈ p r i m e ( 1 − p − s ) = 1 ζ ( s ) \prod_{p\in prime}(1-p^{-s})=\frac 1{\zeta (s)} p∈prime∏(1−p−s)=ζ(s)1
莫比乌斯反演有四种证法，你都知道么
i d ( n ) = n id(n)=n id(n)=n∑ i = 1 ∞ n n s = ∑ i = 1 ∞ 1 n s − 1 = ζ ( s − 1 ) \sum_{i=1}^{\infin}\frac{n}{n^s}=\sum_{i=1}^{\infin}\frac 1{n^{s-1}}=\zeta(s-1) i=1∑∞nsn=i=1∑∞ns−11=ζ(s−1)
类似的有 k k k 次幂函数 i d k ( n ) = n k id_k(n)=n^k idk(n)=nk 的 DGF 是 ζ ( s − k ) \zeta(s-k) ζ(s−k)
欧拉函数 φ \varphi φ∏ p ∈ p r i m e ( 1 + ∑ i = 1 ∞ ( p − 1 ) p i − 1 p i s ) = ∏ p ∈ p r i m e ( 1 + ∑ i = 1 ∞ p i − p i − 1 p i s ) = ∏ p ∈ p r i m e ( 1 + ∑ i = 1 ∞ p i ( 1 − s ) − ∑ i = 1 ∞ p i ( 1 − s ) − 1 ) = ∏ p ∈ p r i m e ( 1 + p 1 − s 1 − p 1 − s − p − s 1 − p 1 − s ) = ∏ p ∈ p r i m e ( 1 + p 1 − s − p − s 1 − p 1 − s ) = ∏ p ∈ p r i m e 1 − p − s 1 − p 1 − s = ζ ( s − 1 ) ζ ( s ) \prod _{p\in prime}\left(1+\sum_{i=1}^{\infin}\frac{(p-1)p^{i-1}}{p^{is}}\right)\\=\prod _{p\in prime}\left(1+\sum_{i=1}^{\infin}\frac{p^i-p^{i-1}}{p^{is}}\right)\\=\prod _{p\in prime}\left(1+\sum_{i=1}^{\infin}p^{i(1-s)}-\sum_{i=1}^{\infin}p^{i(1-s)-1}\right)\\=\prod _{p\in prime}\left(1+\frac{p^{1-s}}{1-p^{1-s}}-\frac{p^{-s}}{1-p^{1-s}}\right)\\=\prod _{p\in prime}\left(1+\frac{p^{1-s}-p^{-s}}{1-p^{1-s}}\right)\\=\prod _{p\in prime}\frac{1-p^{-s}}{1-p^{1-s}}\\=\frac{\zeta(s-1)}{\zeta(s)} p∈prime∏(1+i=1∑∞pis(p−1)pi−1)=p∈prime∏(1+i=1∑∞pispi−pi−1)=p∈prime∏(1+i=1∑∞pi(1−s)−i=1∑∞pi(1−s)−1)=p∈prime∏(1+1−p1−sp1−s−1−p1−sp−s)=p∈prime∏(1+1−p1−sp1−s−p−s)=p∈prime∏1−p1−s1−p−s=ζ(s)ζ(s−1)
约数个数 d d d: ζ 2 ( s ) \zeta^2(s) ζ2(s)约数和 σ \sigma σ: ζ ( s ) ζ ( s − 1 ) \zeta(s)\zeta(s-1) ζ(s)ζ(s−1)然后你就可以发现一些类似于 “欧拉函数卷约数个数等于约数和” 的奇怪的东西。
和 DGF 没啥关系，直接用数论函数暴卷即可，复杂度是 O ( n log n ) O(n\log n) O(nlogn) 的。
或者用一种类似高维前缀和的做法，可以做到 O ( n log log n ) O(n\log\log n) O(nloglogn)，不过没啥用。
设数论函数（注意不是 DGF） F ( n ) , G ( n ) F(n),G(n) F(n),G(n),求 H H H 使得 F = H ∗ G F=H*G F=H∗G
即
F n = ∑ d ∣ n H d G n d F_n=\sum_{d\mid n}H_d G_{\frac nd} Fn=d∣n∑HdGdn
H n G 1 = F n − ∑ d ∣ n , d < n H d G n d H_nG_1=F_n-\sum_{d\mid n,d<n}H_dG_{\frac nd} HnG1=Fn−d∣n,d<n∑HdGdn
算出一个 H n H_n Hn 就暴力枚举倍数更新，复杂度是 O ( n log n ) O(n\log n) O(nlogn)
对每一项
f n n s \frac{f_n}{n^s} nsfn
对 s s s 求导
− ln n ⋅ f n n s -\ln n\cdot\frac{f_n}{n^s} −lnn⋅nsfn
积分
− 1 ln n f n n s -\frac 1{\ln n}\frac{f_n}{n^s} −lnn1nsfn
n = 1 n=1 n=1 要特殊处理一下。
这个 ln \ln ln 不好搞，但我们的求导和积分都是成对出现的，这个 ln \ln ln 一定可以用换底公式消掉，所以我们只需要维护它们的倍数关系就可以了。
也就是说，用来代替的 f f f 只需要满足 f ( 1 ) = 0 , f ( a b ) = f ( a ) + f ( b ) f(1)=0,f(ab)=f(a)+f(b) f(1)=0,f(ab)=f(a)+f(b),且在大于 1 1 1 的数内不能有零点（否则一不小心除数就会变成 0 0 0）。可以用质因子次数和来实现。
连负号都不用加。
ln ( F ( s ) ) = ∫ F ′ ( s ) F ( s ) d s \ln (F(s))=\int \frac{F'(s)}{F(s)}ds ln(F(s))=∫F(s)F′(s)ds
G ( s ) = exp ( F ( s ) ) G ′ ( s ) = F ′ ( s ) exp ( F ( s ) ) = F ′ ( s ) G ( s ) G(s)=\exp(F(s))\\ G'(s)=F'(s)\exp(F(s))=F'(s)G(s) G(s)=exp(F(s))G′(s)=F′(s)exp(F(s))=F′(s)G(s)
设 F , G F,G F,G 对应的数论函数为 f n , g n f_n,g_n fn,gn。
设质因子个数函数为 c n c_n cn（用来代替 ln \ln ln 的那个）
c n g n = ∑ d ∣ n g n d c d f d c_ng_n=\sum_{d\mid n}g_{\frac nd}c_df_d cngn=d∣n∑gdncdfd
d = 1 d=1 d=1 的时候 c d = 0 c_d=0 cd=0 没有贡献，和除法一样算出一个更新一个就可以了。
例题：「EC Final 2019」狄利克雷 k 次根 加强版
后面可能会写点更实际的应用，比如帮你一眼看出怎么卷杜教筛之类的。先咕着。
