莫比乌斯反演及狄利克雷卷积速通
WerChange
·
·
算法·理论
推荐在 cnblogs 上阅读。
莫比乌斯反演速通
前言
由于请假错过了讲课，所以莫反是我第一个需要自学的难度不小的数学知识。
自学的过程的狼狈的，旁边也曾是自学的 czn 告诉我如果学会“狄利克雷卷积”就可以对“莫比乌斯反演”的理解进行“降维打击”。他还十分热心地带着我速通了一遍狄卷与莫反。
一知半解，就自学了很多资料。终于是补全了每一块知识碎片。
秉着造福后人的原则，我想写一篇非常非常通俗易懂的学习笔记。
易懂到什么程度呢？——就是初一的同学，也能速通。
食用指南：备好草稿纸，遇到式子先自己推导，培养推式子的习惯。
数论函数
这是狄利克雷卷积（后文简称“狄卷”）的前置知识。
数论函数是一类这样的函数：定义域为正整数，值域是一个数集。
数论函数间的简单运算有加法与数乘。
- 加法：定义为两个函数逐位相加。(f+g)(n)=f(n)+g(n)。
- 数乘：定义为其函数每位都乘一个数。(xf)(n)=x\cdot f(n)。
狄利克雷卷积
狄卷是数论函数间的运算，记为：
f*g=h
等号左侧展开为：
f*g=\sum\limits_{i|n}f(i)\cdot g(\frac{n}{i})
一些运算律
交换律：f*g=g*f，这个显然。
结合律：(f*g)*h=f*(g*h)，因为：
\sum\limits_{i\cdot j\cdot k=n}(f(i)g(j))\cdot h(k)=\sum\limits_{i\cdot j\cdot k=n}f(i)\cdot (g(j)h(k))
分配律：f*h+g*h=(f+g)*h，因为：
\begin{aligned}
f*h+g*h&=\sum\limits_{i|n}f(i)h(\frac{n}{i})+\sum\limits_{i|n}g(i)h(\frac{n}{i})\\
&=\sum\limits_{i|n} f(i)h(\frac{n}{i})+g(i)h(\frac{n}{i})\\
&=\sum\limits_{i|n} (f(i)+g(i))\cdot h(\frac{n}{i})\\
&=\sum\limits_{i|n} (f+g)(i)\cdot h(\frac{n}{i})\\
&=(f+g)*h
\end{aligned}
一些函数意义
-
性质：$\varphi(1)=1$，$\varphi(n)=n-1$ 当且仅当 $n$ 为质数。
-
定义：
+ $\mu(n)=1$，（$n=1$）
+ $\mu(n)=(-1)^k$，（$n=\prod\limits _{i=1}^{k} p_i$ 且 $p_i$ 为指数为 $1$ 的质数）
+ $\mu(n)=0$，（其他情况）
-
-
-
-
-
这里说明一下第七条，在一些参考书中写作 \mathbf{1}(n)，本文为了区分函数与常数，这里用 I(n) 代替 \mathbf{1}(n)。
一些式子
这里会有很多公式，可以再看证明之前自己先证一遍，难度从易到难。
式子一：(xf)*g=x(f*g)，因为：
\begin{aligned}
(xf)*g&=\sum\limits_{i|n} (xf)(i)\cdot g(\frac{n}{i})\\
&=\sum\limits_{i|n} x\cdot f(i)\cdot g(\frac{n}{i})\\
&=x\cdot \sum\limits_{i|n} f(i)g(\frac{n}{i})\\
&=x(f*g)
\end{aligned}
式子二：f*\epsilon=f，因为：
\begin{aligned}
(f*\epsilon) (n)&=\sum\limits_{i|n} f(i)\epsilon(\frac{n}{i})\\
&=f(n)
\end{aligned}
式子三：I*I=d，因为：
\begin{aligned}
I*I&=\sum\limits_{i|n} I(i)I(\frac{n}{i})\\
&=\sum\limits_{i|n} 1\\
&=d
\end{aligned}
式子四：I*Id_k=\sigma_k，因为：
\begin{aligned}
I*Id_k&=\sum\limits_{i|n} I(i)Id_k(\frac{n}{i})\\
&=\sum\limits_{i|n} Id_k(i)\\
&=\sigma_k
\end{aligned}
式子五：\mu*I=\epsilon，因为：
\begin{aligned}
\mu*I&=\sum\limits_{i|n} \mu(i)I(\frac{n}{i})\\
&=\sum\limits_{i|n} \mu(i)
\end{aligned}
- 当 n=1，显然成立。
- 当 n\neq 1，将 n 分解为 n=p_1^{m_1}p_2^{m_2}\dots p_k^{m_k}。
计算有效的 \mu，肯定质因子的指数为 1。
所以每次在 k 个质因数选择 r 个，即 C_k^r 个。
那就可以继续推式子了。
\begin{aligned}
\sum\limits_{i|n} \mu(i)&=C_k^0-C_k^1+C_k^2-C_k^3+\dots +(-1)^kC_k^k\\
&=\sum\limits_{i=0}^k (-1)^iC_k^i\\
&=(1-1)^k=0
\end{aligned}
因此，\mu *I=\sum\limits_{i|n} \mu(i)=[n=1]=\epsilon。
这里解释一下是怎么得到 (1-1)^k 的：
二项式定理：(x+y)^k=\sum\limits_{i=0}^k C_k^ix^{k-i}y^i。
这里把 x=1，y=-1 带进去得证。
式子六：\varphi*I=Id_1，因为：
设 p 为质数，m>0，则：
\begin{aligned}
(\varphi*I)(p^m)&=\sum\limits_{i|p^m} \varphi(p^m)\\
&=\sum\limits_{i=0}^m \varphi(p^i)\\
&=p^0+\sum\limits_{i=1}^m \varphi(p^i)\\
&=p^0+\sum\limits_{i=1}^m (p^i-p^{i-1})\\
&=p^m
\end{aligned}
因为 n 可分解为 p_1^{m_1}p_2^{m_2}\dots p_k^{m_k}，可由积性函数的性质得证 (\varphi*I)(n)=n=Id_1(n)。
即 \varphi*I=Id_1。
式子七：\varphi=\mu*Id_1。
这个留作作业，答案放在文尾。
简单性质
上文的式子二、四、六就是主要性质，除此之外还有积性函数性质：
若 f，g 为积性函数，则 f*g 也为积性函数。
狄利克雷的逆元
对于每个 f(1)\ne 0 的 f，都存在一个 g 使得 f*g=\epsilon。
如何求 g？
先推一下式子：
\begin{aligned}
f*g&=\sum\limits_{i|n} f(i)g(\frac{n}{i})\\
&=f(1)g(n)+\sum\limits_{i|n,i\ne 1}f(i)g(\frac{n}{i})\\
&=\epsilon=[n=1]
\end{aligned}
现在目标为定义 g(n) 使得等式成立。
可以定义：g(n)=\frac{1}{f(1)}([n=1]-\sum\limits_{i|n,i\ne 1}f(i)g(\frac{n}{i}))。
## 莫比乌斯反演
### 莫比乌斯反演公式
在“狄卷”的“一些函数意义”中我们直接给出了 $\mu$ 的定义与运算方式。
但其实是要推的，仅知道的条件是“定义 $I$ 的逆为 $\mu$”。
让我们来看看如何用狄卷推出莫反的式子——看看狄卷是怎么降维打击的。
如果 $g=f*I$，则
$$
f=f*I*\mu=g*\mu
$$
一展开，即：
如果 $g(n)=\sum\limits_{i|n}f(i)$，则
$$
f(i)=\sum\limits_{i|n}\mu(i)g(\frac{n}{i})
$$
写得优美一点：
$$
g(n)=\sum\limits_{i|n}f(i)\Leftrightarrow f(i)=\sum\limits_{i|n}\mu(i)g(\frac{n}{i})
$$
而这个就是我们的莫反公式了！
别忘了，我们尚未知道 $\mu$ 的值，现在来讲讲怎么求。
由于 $I$ 是积性函数，所以 $\mu$ 也是积性函数。简单算数可得：
$$
\mu(p^k)=\begin{cases}
1 & k=0\\
-1 & k=1\\
0 & k>1
\end{cases}
$$
再根据积性函数，就得到了：
$$
\mu(n)=\begin{cases}
1 & n=1\\
(-1)^k & n=p_1p_2\dots p_k\\
0 & \text{other\ situation}
\end{cases}
$$
于是华丽结束。
有没有体味到降维打击呀朋友们！
### 莫比乌斯函数的性质
如果不讲狄卷，这里应该是第二章，但是学过狄卷的我们可以速通以下三个性质。
1. $\sum\limits_{i|n}\mu(i)=[n=1]$。这个用 $\mu*I=\epsilon$ 秒了。
2. $n=\sum\limits_{i|n}\varphi(i)$。用 $\varphi*I=Id_1$ 秒了。
3. $\sum\limits_{i|n}\frac{\mu(i)}{i} = \frac{\varphi(n)}{n}$。因为 $\varphi=\mu*Id_1$，所以展开得
$\sum\limits_{i|n} \frac{\mu(i)\cdot n}{i}=\varphi(n)\Rightarrow \sum\limits_{i|n} \frac{\mu(i)}{i}=\frac{\varphi(n)}{n}$，秒了。
4. $\mu(n)$ 是积性函数，这个上文解释过了。
### 代码实现预处理 $\mu
```cpp
void init(int x)
{
mu[1]=1;
for(int i=2;i<=x;i++)
{
if(!vis[i])
pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=x;j++)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
}
```
## 参考文献
+ [1]，[Mcggvc](https://www.cnblogs.com/mcggvc)，[《狄利克雷卷积》](https://www.cnblogs.com/mcggvc/p/16900584.html)
+ [2]，[An_Account](https://www.luogu.com/user/39914)，[《莫比乌斯反演-让我们从基础开始》](https://www.luogu.com/article/998kttnc)
+ [3]，[铃悬](https://www.luogu.com.cn/user/18000)，[《铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演》](https://www.luogu.com/article/2sx79hkz)
## 式子七答案
$$
\begin{aligned}
\varphi&=\varphi *\epsilon\\
&=\varphi*I*\mu\\
&=Id_1*\mu
\end{aligned}
$$
## 结尾
有没有感受到用狄卷理解莫反“降维打击”的快感？
由于我是自学的，有一些地方会有纰漏，欢迎指出。
没有例题是因为还没去刷，大家如果想锻炼推式子能力可以看参考文献 2。