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

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) \]

我们有一些比较常用的狄利克雷卷积：

1. \(f* \varepsilon = f\)；
2. \(I *I=\rm{id}\)；
3. \(I*\rm{id}_k=\sigma_k\)；
4. \(\varphi * I=\rm{id}\)。

3. 相关性质

Property 1

狄利克雷卷积具有：

1. 交换律：\(f*g=g*f\)；
2. 结合律：\(f*(g*h)=(f*g)*h\)；
3. 分配律：\(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\)，相当于在高维空间中做了一次差分。

来源链接：https://www.cnblogs.com/XP3301Pipi/p/18804745