莫比乌斯反演

前言

这种神仙玩意儿一听就非常高端。但是如果认真学习的话，还是比想象中的要简单的。

话说本来想拿去装13的却被初三小朋友痛斥过于娱乐…

参考资料

感谢：

莫比乌斯反演学习笔记——by Panda2134

莫比乌斯反演学习笔记——by DimensionTripper

各种能百度到的资料

前置1：数论、积性函数

什么叫数论函数？

在数论上，算术函数（或称数论函数）指定义域为正整数、陪域为复数的函数

——来自百度百科

无法识别的表达方式…

换句话说，数论函数就相当于定义域为$N^+$的函数。

注1：陪域就相当于可以包含值域所有的集合。

如图，如果A是$f(x)$的值域，那么B与C都可以是$f(x)$的陪域。

注2：复数是指形如$z=a+bi$的数…为全部实数与虚数的集合。

什么叫积性函数？

指当$gcd(a,b)=1$时满足$f(ab)=f(a)f(b)$的数论函数。

还有一种更加特殊的情况，即d对于任意$a,b \in Z$时都满足$f(ab)=f(a)f(b)$的函数，被称为完全积性函数。

由于完全积性函数相较于积性函数并没有什么更加可爱的性质，故下文仅对积性函数进行讨论。

有哪些常见的积性函数？

$\mu(n)$：本文主角，莫比乌斯函数。

$$\mu(n)= \begin{cases} \text{1}&&\text{(n==1)}\\ \text{$(-1)^k$}&&\text{(当$n=p_1*p_2*...*p_k$时)}\\ \text{0}&&\text{(当n存在平方因子时)}\\ \end{cases}$$

$1(n)$：不变的函数，恒定值为1

$\epsilon(n)$：单位元，当且仅当$n=1$时$\epsilon(n)=1$，其他情况$\epsilon(n)=0$，即

$$\epsilon(n)= \begin{cases} \text{1}&&\text{(n==1)}\\ \text{0}&&\text{otherwise} \end{cases}$$

$id(n)$：就是$n$的大小，即$id[n]=n$

$\varphi(n)$：欧拉函数，指小于$n$的正整数中与$n$互质数的数目。

$gcd(n,k)$：当$k$固定时，$n$的最大公因子。

$d(n)$：$n$的正因子数目

$σ(n)$：$n$的所有正因子之和

其中加粗的函数与莫比乌斯反演有比较重要的关系。

积性函数的性质

1.对于任意积性函数$f$，$f(1)=1$。

显然，$f(n)=f(n)f(1)\rightarrow f(1)=1$

2.对于一个大于1的正整数$N$，设$N=\prod p_i ^ {a_i}$且$\forall p_i \not= p_j$（就是将$N$质因数分解，则对于一个积性函数$f$：

$$f(n)=f(\prod p_i ^ {a_i})=\prod f(p_i ^ {a_i})$$

根据定义显然。

前置2：狄利克雷卷积

又是一个听起来非常高端的玩意儿…

设$f(n), g(n), h(n)$为数论函数，且

$$h(n)=f(n)*g(n)$$

，则

$$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$$

几条性质

1.交换律：${(f*g)(n)=(g*f)(n)}$；

2.结合律：$((f*g)*h)(n)=(f*(g*h))(n)$；

3.分配律：定义两个数论函数$f(n),g(n)$的加法为逐项相加，即$(f+g)(n)=f(n)+g(n)$，那么$(f+g)*h=f*h+g*h$；

4.积性函数$*$积性函数$=$积性函数，即当$f(n),g(n)$为积性函数时，$h(n)=f(n)*g(n)$也为积性函数。

证明：

设：$n=a*b$，且$gcd(a,b)=1$，则

$$\begin{split} h(n) &&=\sum_{d|n}f(d)g(\frac{n}{d})\\ &&=\sum_{d1|a}\sum_{d2|b}f(d1d2)g(\frac{a}{d1}\frac{b}{d2})\\ &&=\sum_{d1|a}\sum_{d2|b}f(d1)f(d2)g(\frac{a}{d1})g(\frac{b}{d2})\\ &&=\sum_{d1|a}f(d1)g(\frac{a}{d1})\sum_{d2|b}f(d2)g(\frac{b}{d2})\\ &&=h(a)*h(b)\\ \end{split}$$

5.$(f*e)=f$

证明：

$$\begin{split} (f*e)(n)&&=e*f(n)\\ &&=\sum_{d|n}e(d)*f(\frac{n}{d})\\ &&=f(n)\\ \end{split}$$

注：非积性函数亦可卷积。

前置3：莫比乌斯函数

几条性质

1.$\mu(n)$是积性函数

证明：

因为

$$\begin{split} \begin{cases} \mu(p_i^{a_i})=-1&&(a_i==-1)\\ \mu(p_i^{a_i})=0&&(a_i\ge 2)\\ \end{cases} \end{split}$$

所以

$$\mu(n)=\prod p_i^{a_i}$$

由积性函数性质2得：$\mu$是积性函数。

2.$\mu*1=\epsilon$

证明：

因为$\mu$、$1$、$\epsilon$均为积性函数

所以原命题转化为证明：

$$(\mu * 1)(p^k)=\epsilon(p^k)$$

其中

$$(\mu * 1)(p^k)=\sum_{j=0}^{k} \mu(p^j)1(p^{k-j})$$

而

$$\begin{split} \mu(p^j)= \begin{cases} 1 &&(j==0)\\ -1 &&(j==1)\\ 0 &&(j\ge 2)\\ \end{cases} \end{split}$$

所以

$$\begin{split} \sum_{j=0}^{k} \mu(p^j)1(p^{k-j})= \begin{cases} 1-1+0+0+0...&&(k>0)\\ 1&&(k==0) \end{cases} \end{split}$$

即原命题成立

该命题还有另一种表达方式：

$$\sum_{d|n} \mu(d)=[n==1]$$

因为：

$$\sum_{d|n}\mu(d)=\sum_{d|n}\mu(d)*1=(\mu*1)(n)=\epsilon(n)$$

注：其中$[$   $]$ 表示艾佛森括号，方括号其中的条件满足则为1，不满足则为0，即：

$$\begin{aligned}\\ [P]&=1 &\text{(If P is true)}\\ [P]&=0 &\text{(Otherwise)} \end{aligned}$$

正题：莫比乌斯反演

形式一：已知$f(x),g(x)$为两个数论函数，如果

$$f(n)=\sum_{d|n}g(d)$$

则

$$g(n)=\sum_{d|n}f(d)*\mu(\frac{n}{d})$$

证明1：（狄利克雷卷积法）

已知

$$f(n)=\sum_{d|n}g(d)$$

改写成卷积的形式

$$f(n)=g(n)*1$$

等式两侧同时$*\mu$

$$f*\mu=g*1*\mu$$

由莫比乌斯函数性质知：$\mu*1=\epsilon$，
即

$$f*\mu=g*\epsilon=g$$

根据狄利克雷卷积展开，则

$$g(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$$

证明2：(定义法)

由$f(n)$的定义知：

$$\begin{aligned} \sum_{d|n}\mu(d)f(\frac{n}{d})=&\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}g(i)\\ =&\sum_{d|n}\sum_{i|\frac{n}{d}}\mu(d)g(i)\\ =&\sum_{i|n}\sum_{d|\frac{n}{i}}\mu(d)g(i)\\ =&\sum_{i|n}g(i)\sum_{d|\frac{n}{i}}\mu(d)\\ \end{aligned}$$

根据莫比乌斯函数的性质：当且仅当$\frac{n}{i}==1$时，
$\sum_{d|\frac{n}{i}}\mu(d)=1$，所以：

$$\sum_{i|n}g(i)\sum_{d|\frac{n}{i}}\mu(d)=g(n)$$

形式二：
如果

$$g(n)=\sum_{n|d}f(d)$$

那么

$$f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)$$

证明：

$$\begin{aligned} \sum_{n|d}\mu(\frac{d}{n})g(d)=&\sum_{k=1}^{+\infty}\mu(k)g(nk)\\ =&\sum_{k=1}^{+\infty}\mu(k)\sum_{nk|t}f(d)\\ =&\sum_{n|t}f(t)\sum_{k|(t|n)}\mu(k)\\ =&\sum_{n|t}f(t)[t==n]\\ =&f(n) \end{aligned}$$

---

具体实现咕到下篇博客里…