学好数理化，走遍天下都不怕

编程中的较高端的数论知识总结2--狄利克雷卷积

发表于 更新于 分类于

注意！！！请务必先阅读完（或学会）莫比乌斯反演，文章中默认大家都已经看过了

一些新的表示

在这篇博客中，为了节省篇幅，也方便读者们学习，我会使用以下的这样简便的写法，当然这在数论中也是允许的，只是个人认为不是很规范，最好还是写清楚：

  1. 我们用$f$来代替数论函数$f(n)$，但是在$n$说表示一个具体的数时，还是会写成$f(n)$的形式
  2. $f+g$表示两个数论函数相加，减号也采用相同的写法，$f+g$的具体定义是：$(f+g)(n)=f(n)+g(n)$，减号相同
  3. $xf$表示数论函数乘上一个倍数，具体是：$(xf)(n)=x\cdot f(n)$

    狄利克雷卷积是个啥

    是数论函数的重要运算之一
    设$f(n)$、$g(n)$是两个数论函数，它们的狄利克雷乘积也是一个数论函数，简记为$h(n)=f(n)*g(n)$
    ——百度百科，有删改

哦，看了这个定义，好像没看出什么名堂来……
其实还是有的：

  1. 两个数论函数的狄利克雷卷积也是一个数论函数额，好像是废话
  2. 狄利克雷卷积在数论中就相当于乘法，因为它的表示符号就是乘号（星号，不能写成点乘或者叉乘的符号）

所以，到底怎么计算呢？
是这样的：$h(n)=\sum\limits_{d|n}f(d)g\left(\frac{n}{d}\right)$
有时，我们也会把它写成：$h(n)=\sum\limits_{d_1d_2=n}f(d_1)g(d_2)$
显然，这两个东西是等价的……
除了把它简写成$h(n)=f(n)g(n)$，我们当然也可以像前面一样，把它写成：$h=fg$
在后文中，我就采用这种最简单的写法

性质

既然是个运算，肯定得有些性质吧，我们先来看看最基本的三个性质中，它满足什么

  1. 交换律：$fg=gf$，满足
    证明：$(fg)(n)=\sum\limits_{d_1d_2=n}f(d_1)g(d_2)=\sum\limits_{d_2d_1=n}f(d_2)g(d_1)=(gf)(n)$
  2. 结合律：$f(gh)=(fg)h$，满足
    证明：$(f(gh))(n)=\sum\limits_{d_1d_2=n}f(d_1)(gh)(d_2)=\sum\limits_{d_1d_2=n}f(d_1)\sum\limits_{d_3d_4=d_2}g(d_3)h(d_4)=\sum\limits_{d_1d_2d_3=n}f(d_1)g(d_2)h(d_3)=\sum\limits_{d_2d_3d_1=n}f(d_2)g(d_3)h(d_1)=(h(fg))(n)=((fg)*h)(n)$
  3. 分配律：$f(g+h)=fg+fh$，满足
    证明：$(f    (g+h))(n)=\sum\limits_{d_1d_2=n}f(d_1)(g(d_2)+h(d_2))=\sum\limits_{d_1d_2=n}f(d_1)g(d_2)+\sum\limits_{d_1d_2=n}f(d_1)h(d_2)=(fg)(n)+(fh)(n)=(fg+fh)(n)$

好的，这三个基本性质好像都满足，看起来好像真的很像乘法耶！
还有什么性质吗？有！

  1. $(xf)g=x(fg)$
    证明：$((xf)g)=\sum\limits_{d_1d_2=n}xf(d_1)g(d_2)=x\sum\limits_{d_1d_2=n}f(d_1)g(d_2)=(x(fg))(n)$
    注意，这并不能用上面的分配律来证明，因为这是数字乘以函数，而不是函数乘以函数
  2. $\epsilonf=f$（$\epsilon$就是之前说过的单位元，即$\epsilon(n)=[n==1]$）
    证明：$(\epsilon    f)(n)=\sum\limits_{d_1d_2=n}f(d_1)\epsilon(d_2)=\sum\limits_{d_1d_2=n}f(d_1)[d_2==1]=f(n)$
  3. 我们定义数论函数$f$的逆元指的是满足$fg=\epsilon$的数论函数$g$，下面我们求证：对于任意数论函数$f$，它都有逆元$g$
    证明：$(f    g)(n)=f(1)g(n)+\sum\limits_{d|n,d\neq1}f(d)g\left(\frac{n}{d}\right)=[n==1]$
    $\therefore f(1)g(n)=[n==1]-\sum\limits_{d|n,d\neq1}f(d)g\left(\frac{n}{d}\right)$
    $\therefore g(n)=\frac{1}{f(1)}\left([n==1]-\sum\limits_{d|n,d\neq1}f(d)g\left(\frac{n}{d}\right)\right)$
    $\therefore$对于任意数论函数$f$，它都有逆元$g$，且$g(n)=\frac{1}{f(1)}\left([n==1]-\sum\limits_{d|n,d\neq1}f(d)g\left(\frac{n}{d}\right)\right)$
  4. 两个积性函数的狄利克雷卷积也是积性函数
    证明：设$f,g$为积性函数，$gcd(m,n)=1$
    $\therefore (fg)(mn)=\sum\limits_{d|mn}f(d)g\left(\frac{mn}{d}\right)=\sum\limits_{d_1|m,d_2|n}f(d_1d_2)g\left(\frac{mn}{d_1d_2}\right)=\sum\limits_{d_1|m,d_2|n}f(d_1)f(d_2)g\left(\frac{m}{d_1}\right)g\left(\frac{n}{d_2}\right)=\left(\sum\limits_{d_1|m}f(d_1)g\left(\frac{m}{d_1}\right)\right)\left(\sum\limits_{d_2|n}f(d_2)g\left(\frac{n}{d_2}\right)\right)=(fg)(m)(f*g)(n)$

    再谈莫比乌斯反演

    等等，莫比乌斯反演不是之前讲过了吗？为啥这里还有？
    因为学了狄利克雷卷积后，我们对莫比乌斯反演又有了新的认识
    先来回顾一下莫比乌斯反演的式子：$f(n)=\sum \limits_{d|n}\mu(d)F\left(\frac{n}{d}\right)$
    看出什么名堂来了吗？
    如果还没有的话，我再把狄利克雷卷积的式子写一下：$(fg)(n)=\sum\limits_{d|n}f(d)g\left(\frac{n}{d}\right)$
    看出来了吧！
    把狄利克雷卷积的式子中的$f$替换成$\mu$，把$g$替换成$F$，你就会（惊奇？）地发现：$f=\mu    F$！！！
    用同样的方法，我们来看看$F$的定义：$F(n)=\sum \limits_{d|n}f(d)$
    你又会（惊奇？）地发现：$F=fI$（还记得$I$函数吗？$I(n)=1$）
    所以，我们会发现：$(\epsilon    f)(n)=f(n)=(\muF)(n)=(\muIf)(n)$
    所以$\mu    I=\epsilon$！
    我们找到了$\mu$函数的第二种定义方式——$I$函数的逆元
    现在，我们来证明$\mu$是$I$函数的逆元
    证明：$\mu(n)=[n==1]-\sum\limits_{d|n}\mu(d)+\mu(n)=[n==1]-\sum\limits_{d|n,d\neq n}\mu(d)=[n==1]-\sum\limits_{d|n,d\neq1}\mu\left(\frac{n}{d}\right)=\frac{1}{I(1)}\left([n==1]-\sum\limits_{d|n,d\neq1}I(d)\mu\left(\frac{n}{d}\right)\right)$
    $\therefore \mu$是$I$函数的逆元
    其中，第一步用到了莫比乌斯函数的性质一

    常见计算

  5. $\mu*I=\epsilon$：上已证明
  6. $I\varphi=id$：
    设$n=\prod\limits_{i=1}^kp_i^{\alpha_i}$
    $\therefore 1\sim n$的数可以分为许多不同的集合，其中$A_{(\beta_1,\beta_2,\cdots,\beta_k)}=\{p\prod\limits_{i=1}^kp_i^{\beta_i}|gcd(p,\prod\limits_{i=1}^kp_i^{(\alpha_i-\beta_i)})=1\}$
    $\therefore \left|A_{(\beta_1,\beta_2,\cdots,\beta_k)}\right|=\varphi\left(\prod\limits_{i=1}^kp_i^{(\alpha_i-\beta_i)}\right)$
    $\therefore n=\sum\limits_{\beta_i\leqslant \alpha_i}\varphi\left(\prod\limits_{i=1}^kp_i^{(\alpha_i-\beta_i)}\right)=\sum\limits_{d|n}\varphi(d)$
    $\therefore id=\varphi    I$
  7. $\muid=\varphi$：
    $\because id=\varphi    I$
    $\therefore \varphi=id*\mu$
  8. $II=\tau$：
    $\because \tau=\sum \limits_{d|n}1$
    $\therefore I    I=\tau$
  9. $Iid=\sigma$
    $\because \sigma=\sum \limits_{d|n} d$
    $\therefore I    id=\sigma$

    实际应用

    单独只用到狄利克雷卷积的题目很少（至少我没做过），一般都会和其他的知识，如杜教筛、莫比乌斯反演等结合，狄利克雷卷积只是中间计算的工具
    所以，在实际做题时，可以结合狄利克雷卷积进行计算

相关文章：

  1. 编程中的较高端的数论知识总结1——莫比乌斯反演