DGF

感觉还是不够深刻?

Posted by ShanLunjiaJian's Blog on May 19, 2021

以下如无特殊说明,默认数论函数贴在一起的乘法和乘方都是点积,除法是狄利克雷除法。

DGF是什么

DGF定义为

\[\tilde{F}(z)=\sum_{i=1}^\infty\frac{f_i}{i^z}\]

。容易发现它的卷积就是狄利克雷卷积。

常见的DGF

最基本的DGF是黎曼函数\(\zeta=\sum_{i=1}\frac{1}{i^z}\),它也是恒等函数\(\mathbf{1}\)的DGF。

对于常见积性函数,我们可以通过对每个质因子分开计算贡献,利用\(\zeta\)得到DGF的简洁式子。在此之前,我们先看看\(\zeta\)的另一种形式 :

\[\begin{aligned} \zeta&=\sum_{i=1}\frac{1}{i^z}\\ &=\prod_{p\in P}\sum_{i=1}\frac{1}{p^{iz}}\\ &=\prod_{p\in P}\frac{1}{1-p^{-z}} \end{aligned}\]

然后就比较简单。分别是\(\epsilon,\mu,\mu^2,\mathrm{id}_k,\varphi,\sigma_k\)的DGF \(\tilde{E},\tilde{M},\tilde{M}_2,\tilde{ID}_k,\tilde{\varPhi},\tilde{\Sigma}_k\)。说实话这里把LaTeX换成HTML-CSS模式更好看,并且亲测没问题。

\[\begin{aligned} \tilde{E}&=1\\ \\ \tilde{M}&=\prod_{p\in P}\left(1+\frac{-1}{p^z}\right)\\ &=\prod_{p\in P}(1-p^{-z})=\frac{1}{\zeta}\\ \\ \tilde{M}_2&=\prod_{p\in P}\left(1+p^{-z}\right)\\ &=\prod_{p\in P}\frac{1-p^{-2z}}{1-p^{-z}}=\frac{\zeta(z)}{\zeta(2z)}\\ \\ \tilde{ID}_k&=\sum_{i=1}\frac{i^k}{i^z}\\ &=\sum_{i=1}\frac{1}{i^{z-k}}=\zeta(z-k)\\ \\ \tilde{\varPhi}&=\prod_{p\in P}\left(1+\sum_{i=1}\frac{p^i-p^{i-1}}{p^{iz}}\right)\\ &=\prod_{p\in P}\left(1+\sum_{i=1}\frac{p^i}{p^{iz}}-\sum_{i=1}\frac{p^{i-1}}{p^{iz}}\right)\\ &=\prod_{p\in P}\left(1+\sum_{i=1}p^{-i(z-1)}-\sum_{i=1}p^{-i(z-1)-1}\right)\\ &=\prod_{p\in P}\left(1+\frac{p^{1-z}}{1-p^{1-z}}-\frac{p^{-z}}{1-p^{1-z}}\right)\\ &=\prod_{p\in P}\left(\frac{1-p^{-z}}{1-p^{1-z}}\right)=\frac{\zeta(z-1)}{\zeta(z)}\\ \\ \tilde{\Sigma}_k&=\prod_{p\in P}\sum_{i=0}\frac{\sum_{j=0}^ip^{jk}}{p^{iz}}\\ &=\prod_{p\in P}\sum_{i=0}\frac{1-p^{(i+1)k}}{(1-p^k)p^{iz}}\\ &=\prod_{p\in P}\frac{1}{1-p^k}\left(\sum_{i=0}\frac{1}{p^{iz}}-\sum_{i=0}\frac{p^{ik+k}}{p^{iz}}\right)\\ &=\prod_{p\in P}\frac{1}{1-p^k}\left(\sum_{i=0}p^{-iz}-p^k\sum_{i=0}p^{-i(z-k)}\right)\\ &=\prod_{p\in P}\frac{1}{1-p^k}\left(\frac{1}{1-p^{-z}}-\frac{p^k}{1-p^{k-z}}\right)\\ &=\prod_{p\in P}\frac{1-p^{k-z}-p^k+p^{k-z}}{(1-p^k)(1-p^{-z})(1-p^{k-z})}\\ &=\prod_{p\in P}\frac{1-p^k}{(1-p^k)(1-p^{-z})(1-p^{k-z})}\\ &=\prod_{p\in P}\frac{1}{(1-p^{-z})(1-p^{k-z})}\\ &=\zeta(z)\zeta(z-k) \end{aligned}\]

。实际上这些有一些可以用一些恒等式推出来,但是做一做等比数列求和的练习也没啥问题是吧(

呃你问什么恒等式?\(\varphi=\mathrm{id}\ast\mu,\sigma_k=\mathbf{1}\ast\mathrm{id}_k\),可以帮我们省去 害 怕 的等比数列求和。我**求了一下午的等比数列和,那个\(\tilde{\Sigma}_k\)真的恶心。

乘法

乘法很简单,因为直接狄利克雷卷积就是一个\(\log\)的。

乘法逆

推推式子然后递推。

假设我们要求\(\tilde{G}=\frac{1}{\tilde{F}}\),那就相当于求\(\tilde{E}=\tilde{F}\ast\tilde{G}\),

\[\begin{aligned} \tilde{E}&=\tilde{F}\ast\tilde{G}\\ \epsilon(n)&=\sum_{d\mid n}g(d)f(\frac{n}{d})\\ &=g(n)f(1)+\sum_{d\mid n,d<n}g(d)f(\frac{n}{d})\\ g(n)&=\frac{1}{f(1)}\left(\epsilon(n)-\sum_{d\mid n,d<n}g(d)f(\frac{n}{d})\right) \end{aligned}\]

预处理因数可以做到\(O(n\log n)\)。更简单的方法是枚举因数,计算它对它倍数的贡献,这样复杂度也是\(O(n\log n)\)。

好像没有狄利克雷带余除法这种东西,直接乘\(\mathrm{inv}\)就是除法了。

\(\ln\)和\(\exp\)

要做\(\ln\),我们还是直接导完了\(\mathrm{inv}\),然后积回去。现在问题变成了怎么求导/积分。

求导的话,你发现\(\frac{\mathrm{d}\frac{1}{n^z}}{\mathrm{d}z}=-\frac{\ln n}{n^z}\),但是这个\(\ln n\)咋搞?

如果我们只要$\ln F+\ln G=\ln(FG)$呢?一个厉害做法是,考虑找一个性质足够强并且好计算的导数的类似物,我们要$\ln F+\ln G=\ln(FG)$,也就是$F^\prime G+FG^\prime=(FG)^\prime$。代入dgf的形式我们知道只要有$\ln a+\ln b=\ln ab$即可,也就是说我们只需要一个完全加性函数作为$\ln$,并且除了$\ln 1=0$之外它必须非$0$以可逆,素因数次数和$\Omega$是满足这个要求的。

具体说明一下为什么只要有$\ln a+\ln b=\ln ab$即可。$F^\prime G+FG^\prime=(FG)^\prime$,两边提取$[\frac{1}{n^z}]$,我们知道左边就是$\sum\limits_{ij=n}f(i)g(j)(\ln i+\ln j)$,而右边就是$\sum\limits_{ij=n}f(i)g(j)\ln ij$。

然后是积分,\(\int\frac{1}{n^z}\ \mathrm{d}z=-\frac{1}{n^z\ln n}+C\),这就非常好,于是我们已经会\(\ln\)了。

\(\exp\)呢?直接干翻式子 :

\[\begin{aligned} G&=\exp(F)\\ G^\prime&=\exp(F)F^\prime=GF^\prime\\ -g(n)\ln n&=-\sum_{d\vert n}f(d)g(\frac{n}{d})\ln d\\ g(n)&=\frac{\sum_{d\vert n}f(d)g(\frac{n}{d})\ln d}{\ln n}\\ \end{aligned}\]

,核心是用求导把看不见摸不着的\(\exp\)转化成卷积。当然也可以通过枚举因数计算贡献得到一个很简单的实现。

推式子

DGF的主要作用还是推式子,因为不会有人毒瘤到让你写狄利克雷快速幂的/jy

这部分并没有例题/jy

和线性筛

有时候DGF大力推式子可以给出一些积性函数的简单线性筛方法。

咋推?根据DGF可以瞬间得到一个质数幂的贡献,而知道了这个我们就可以线筛了。


例题1.1

线性筛\(\phi\ast\mu\)。

它的DGF就是\(\frac{\zeta(z-1)}{\zeta^2(z)}\)。

展开回去,我们知道

\[\frac{\zeta(z-1)}{\zeta^2(z)}=\prod_{p\in P}\frac{(1-p^{-z})^2}{1-p^{1-z}}=\prod_{p\in P}\left(1+\frac{-2}{p^z}+\frac{1}{p^{2z}}\right)\left(\frac{p}{p^z}+\frac{p^2}{p^{2z}}+...\right)\]

\(p^e\)的贡献,就是\(\frac{1}{p^{ez}}\)前的系数。要求这个东西,显然考虑前面那个括号里面,三个东西选哪一个,然后加起来。选\(1\)则得\(p^e\),选\(\frac{-2}{p^z}\)则得\(-2p^{e-1}\),选\(\frac{1}{p^{2z}}\)则得\(p^{e-2}\),所以总贡献就是\(p^e-2p^{e-1}+p^{e-2}\)。注意\(e=0,1\)需要特判。

和亚线性筛

杜教筛构造\(f\ast g=h\),对应到DGF就是\(\tilde{F}\tilde{G}=\tilde{H}\)。比如你看到\(\tilde{F}=\tilde{\varPhi}=\frac{\zeta(z-1)}{\zeta(z)}\),你就知道构造\(\tilde{G}=\tilde{ID}_0=\zeta(z),\tilde{H}=\tilde{ID}_1=\zeta(z-1)\)。非常简单。

Powerful Number可以处理,或者说它的一部分是处理形如

\[\tilde{F}=\prod_{p\in P}\left(1+\sum_{i=2}\frac{\cdots}{p^{iz}}\right)\]

的函数,因为它们只在Powerful Number处有值。如果在推式子过程中见到了这种东西,可以试一试PN。