狄利克雷卷积与莫比乌斯反演

狄利克雷卷积与莫比乌斯反演

1. 基本数论函数

常函数：\(I(n)=1\)；
恒等函数：\(\operatorname{id_k}(n)=n^k\)；\(\operatorname{id}_1(n)\) 记为 \(\operatorname{id}(n)\)。
约数函数：\(\sigma_k(n)=\sum_{d\mid n} d^k\)；\(\sigma_0(n)\) 记为 \(\rm{d}(n)\)，\(\sigma_1(n)\) 记为 \(\sigma(n)\)；
单位函数：\(\varepsilon(n)=[n=1]\)。
可以证明，这些函数都是积性函数。证明可以参见其他博文，此处不作为重点。
若一个数论函数 \(f\) 为积性函数，那么 \(f(1)\times f(1)=f(1)\)，即 \(f(1)=1\) 或 \(0\)。
当 \(f(1)=0\) 时，\(f(x)=f(1) \times f(x)=0\)，那么该函数为全 \(0\) 函数，没有讨论价值。
所以我们约定，下文中讨论的积性函数都满足 \(f(1)=1\)。
2. 狄利克雷卷积

现有两个数论函数 \(f,g\)。
定义 \(h=f*g\) 为：

\[h(n)=\sum_{d\mid n} f(d)g(\frac{n}{d})\]
并称 \(h\) 为 \(f,g\) 的狄利克雷卷积。
狄利克雷卷积还有更为对称的形式：

\[h(n)=\sum_{xy=n} f(x)g(y)\]
我们有一些比较常用的狄利克雷卷积：

• \(f* \varepsilon = f\)；
  
• \(I *I=\rm{id}\)；
  
• \(I*\rm{id}_k=\sigma_k\)；
  
• \(\varphi * I=\rm{id}\)。
  

3. 相关性质

Property 1

狄利克雷卷积具有：

• 交换律：\(f*g=g*f\)；
  
• 结合律：\(f*(g*h)=(f*g)*h\)；
  
• 分配律：\(f*(g+h)=f*g+f*h\)；
  

证明比较简单，此处略去。
由此可以得出一些其他结论：$\sigma=I * {\rm id}=I * I * \varphi ={\rm d} * \varphi $。
Property 2

若 \(f,g\) 为积性函数，则 \(f*g\) 也为积性函数。

设 \(n\perp m\)，\(h=f*g\)，那么：

\[\begin{aligned}h(nm)&=\sum_{d\mid nm} f(d)g(\dfrac {nm} d)\\&= \sum_{x\mid n,y\mid m}f(xy)g(\dfrac{nm}{xy})\\&= \sum_{x\mid n,y\mid m} f(x)f(y)g(\dfrac n x)g(\dfrac my )\\&= (\sum_{x\mid n} f(x)g(\dfrac n x))(\sum_{y\mid m}f(y)g(\dfrac m y))\\&= h(n)h(m)\end{aligned}\]

4. 狄利克雷逆

若数论函数 \(f,g\) 满足 \(f*g=\varepsilon\)，则称 \(g\) 为 \(f\) 的狄利克雷逆，记为 \(g=f^{-1}\)。
对于一个 \(f\)，考虑如何求出 \(f^{-1}\)。
当 \(n=1\) 时，\(f(1)g(1)=\varepsilon(1)=1\)，则有 $g(1)=\dfrac 1 {f(1)} $。
当 \(n>2\) 时，

\[\begin{aligned}\sum_{d\mid n}f(d)g(\dfrac n d)=\varepsilon(n)&=0\\f(1)g(n)+\sum_{d>1,d\mid n} f(d)g(\dfrac n d)&=0\\g(n)=-\dfrac 1{f(1)}\sum_{d>1,d\mid n} f(d)g(\dfrac n d)\end{aligned}\]
由上式可以看出，\(f\) 有狄利克雷逆的充要条件是 \(f(1)\ne 0\)。
若 \(f\) 为积性函数，则 \(f^{-1}\) 也为积性函数。证明比较复杂，此处不作赘述。
若 \(f*g=h\)，且 \(f^{-1}\) 存在，则 $ g=h*f^{-1}$。

\(f*g=h*\varepsilon = h*f*f^{-1} \Rightarrow g=h*f^{-1}\)。

若 \(f^{-1}\) 与 \(g^{-1}\) 均存在，则 \((f*g)^{-1}=f^{-1}*g^{-1}\)。

\((f*g)^{-1}*(f*g)=f^{-1}*g^{-1}*(f*g)=\varepsilon\)。

5. 莫比乌斯函数/反演

定义莫比乌斯函数 \(\mu\) 为 \(I\) 的狄利克雷逆，即 \(\mu * I=\varepsilon\)。所以 \(\mu\) 也是积性函数。
由定义得，\(\sum_{d\mid n}\mu(d)=[n=1]\)。
考虑如何求出 \(\mu(n)\)。不妨先对于一个质数 \(p\) 考虑 \(\mu(p^k)\) 的值。
首先我们有 \(\mu(1)=1\)。
\(\mu(p)I(1)+\mu(1)I(p)=\mu(1)+\mu(p)=\varepsilon(p)=0\)，得到 \(\mu(p)=-\mu(1)=-1\)。
\(\mu(1)I(p^2)+\mu(p)I(p)+\mu(p^2)I(1)=\mu(1)+\mu(p)+\mu(p^2)=\varepsilon(p^2)=0\)，得到 \(\mu(p^2)=0\)。
以此类推，可以发现，当 \(k\geq 2\) 时，\(\mu(p^k)\) 都是 \(0\)。
对于一般的 \(n\)，我们对其做唯一分解，\(n=\prod p_i^{c_i}\)，则 \(\mu(n)=\prod \mu(p_i^{c_i})\)。
我们可以得到：

\[\mu(n)=\begin{cases}1 &n=1\\0& \exists p>1,p^2\mid n\\(-1)^{\omega(n)} &otherwise\end{cases}\]
现在，我们可以得到莫比乌斯反演的形式了：

\[g=f*I \Leftrightarrow f=g*\mu\]
将其展开：

\[g(n)=\sum_{d\mid n} f(n) \Leftrightarrow f(d)=\sum_{d\mid n} g(d) \mu(\dfrac n d)=\sum_{d\mid n} \mu(d)g(\dfrac n d)\]
有了莫比乌斯反演，我们就能得出更多的结论。
例如：$ \varphi* I={\rm id}\Rightarrow \varphi = {\rm id}*\mu $。
6. 莫比乌斯函数与容斥原理

我们考虑从组合数学的角度来理解莫比乌斯函数。
考虑这样一个问题：\([1,30]\) 内有多少数字不是 \(2,3,5\) 的倍数？
那么根据容斥原理，答案就是 \(30\) 分别减去 \(2,3,5\) 的倍数个数， 再分别加上 \(6,10,15\) 的倍数个数，最后减去 \(30\) 的倍数个数。
进一步考虑：给定 \(n\)，设所有 \(\leq n\) 质数为 \(p_1,p_2,p_3,\cdots,p_k\)，在 \([1,n]\) 中有多少数字不是任意一个 \(p_i\) 的倍数？
同样根据容斥原理，答案是 \(n-\sum_{\varnothing \subset S\subseteq \{1,2,3,\cdots,k\}} (-1)^{|S|}\lfloor \dfrac{n}{\prod_{j\in S}p_j} \rfloor\)。最终只有 \(1\) 会剩下来。
注意到每个质数集合前面带的系数恰好为 \(\mu(\prod(p_j))\)。上式也可以写为：

\[\sum_{i=1}^n \mu(i)\lfloor\dfrac n i \rfloor\]
再进一步，对正整数集考虑，如果我们只想要留下 \(1\)，那么可以考虑下面的容斥：

• 加上所有 \(1\) 的倍数；
  
• 减去所有 \(2,3,5,7,\cdots\) 等质数的倍数；
  
• 加上所有 \(6,10,14,15,\cdots\) 等两个质数乘积的倍数；
  
• \(\cdots\)
  

所以，$\mu(n) $ 可以看作对正整数集做容斥时，\(n\) 前面所带的系数。
我们同样可以从组合的角度来理解 \(\mu\) 的卷积定义。
设 \(n\) 有 \(k\) 个不同质因子 \(p_1,p_2,p_3,\cdots,p_k\)。那么：

\[\sum_{d\mid n}\mu(n)=\sum_{S\subseteq \{1,2,3,\cdots,k\}} \mu(\prod_{j\in S}p_j)=\sum_{i=0}^k\binom k i (-1)^i=(1-1)^k=0\]
7. 狄利克雷前缀和

考虑当 \(f\) 已知时，如何求出 \(g=f*I\) 。
我们可以枚举 \(x\) 的倍数 \(kx\)，将 \(f(x)\) 贡献到 \(g(kx)\)。时间复杂度 \(O(n\log n)\)。
实际上，利用狄利克雷前缀和，我们可以做到更优的复杂度。
将卷积式子展开，\(g(n)=\sum_{d\mid n} f(d)\)。
\(d\mid n\) 的一个充要条件是，对于每一个质数 \(p\)，其在 \(d\) 中的次数 \(c_d\) 都不超过在 \(n\) 中的次数 \(c_n\)。
所以，我们把每一个质数看作一维，质数的次数看作坐标。那么每一个自然数都可以看作在高维空间空间中的一个点，\(g(n)\) 的值就是在这个高维空间中 \(f\) 的前缀和。
首先令 \(g(x)=f(x)\)。类似于高维前缀和，我们枚举每个质数 \(p\)，令 \(g(x)\) 贡献到 \(g(xp)\)。这就相当于对这一维做了一次前缀和。
对于一个质数 \(p\)，需要枚举 \(\frac n p\) 个数字。那么这样的总时间复杂度为 \(\sum\frac n p=O(n\log \log n)\)。
同理，求 \(g=f*\mu\)，相当于在高维空间中做了一次差分。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！