莫比乌斯反演

约定

\([x]\) 为逻辑判断函数，若 \(x\) 为真则 \([x]=1\) 否则为 \(0\)

积性函数

对于一个数论函数 \(f\)。若当 \(gcd(i,j)=1\) 时，满足 \(f(i\times j)=f(i)\times f(j)\) 则称 \(f\) 为积性函数。

若对于任意 \(i,j\) 满足 \(f(i\times j)=f(i)\times f(j)\) 则称 \(f\) 为完全积性函数。

常见的积性函数：

单位元函数 \(\epsilon(n)=[n=1]\)

乘法单位元函数 \(E(n)=1\)

莫比乌斯函数 \(\mu(n)\)

欧拉函数 \(\varphi(n)\)

狄利克雷卷积

设 \(f,g\) 为两个数论函数，则卷积运算定义为：

\[(f*g)(n)=\sum_{d|n}{f(d)\times g(\frac{n}{d})} \]

也可以写成：

\[(f*g)(n)=\sum_{ij=n}f(i)\times g(j) \]

这个卷积满足交换律结合律。

交换律：由定义显然可知。

结合律：

\[\begin{aligned} (h*(f*g))(n)&=\sum_{pk=n}(\sum_{ij=p}f(i)\times g(j)))\times h(k) \\ (h*(f*g))(n)&=\sum_{ijk=n}f(i)\times g(j)\times h(k) \end{aligned} \]

定义乘法单位元函数 \(E\) 有 \(E(i)=1\)。那么就有：

\[\begin{aligned} (f*E)(n)&=\sum_{d|n}{f(d)\times E(\frac{n}{d})} \\ (f*E)(n)&=\sum_{d|n}{f(d)} \end{aligned} \]

定义单位元函数 \(\epsilon(n)=[n=1]\)。那么就有：

\[\begin{aligned} (f*\epsilon)(n)&=\sum_{d|n}{f(d)\times \epsilon(\frac{n}{d})} \\ (f*\epsilon)(n)&=f(n) \end{aligned} \]

逆元

将 \(f\) 在狄利克雷卷积意义下的逆元记作 \(f^{-1}\)。定义 \((f*f^{-1})(n)=\epsilon(n)\)

莫比乌斯函数

设 \(n=\prod{p_i^{c_i}}\) 其中 \(c>0\) 而 \(p_i\) 为质数。

定义 \(\mu(n)\) 函数为：

\[\mu(n)= \left\{ \begin{aligned} 1& &n=1 \\ (-1)^m& &\not\exist c_i>1 \\ 0& &\exist c_i>1 \end{aligned} \right. \]

说人话就是，如果 \(n\) 的某一个质因子的个数大于 \(1\) 那么 \(\mu(n)=0\) 。否则 \(\mu(n)=(-1)^m\) ，\(m\) 表示 \(n\) 的质因子个数。特殊地，我们定义 \(\mu(1)=1\)。

结论：莫比乌斯函数的逆元是 \(E\) 。

即有 \((\mu*E)(n)=\epsilon(n)\)。

证明：

设 \(n=\prod_{i=1}^m p_i^{c_i}\)。

\[\begin{aligned} (\mu*E)(n)&=\sum_{d|n}\mu(d)\times E(\frac{n}{d}) \\ &=\sum_{d|n}\mu(d) \\ &=\sum_{i=0}^{m}{\dbinom{m}{i}(-1)^i} \\ &=\sum_{i=0}^{m}{\dbinom{m}{i}(-1)^i(1)^{m-i}} \\ &=(-1+1)^m \\ &= 0 \end{aligned} \]

特殊地，\((\mu*E)(1)\) 显然为 \(1\)。

也就是说 \((\mu*E)(n)=[n=1]\) 。

那么可得 \((\mu*E)(n)=\epsilon\) 。