莫比乌斯反演 学习笔记

注：以下内容源自各种各样的资料，不保证正确性，仅供参考。

约定 \(*\) 代表运算“卷”，部分出现的 \(1\) 代表常数函数。

莫比乌斯函数

\(\mu\) 为莫比乌斯函数，定义为： \[ \mu(n)=\begin{cases} 1 & n=1 \\ 0 & n\text{含有平方因子}\\ (-1)^k & k\text{为}n\text{的本质不同质因子个数} \end{cases} \] 莫比乌斯函数是积性函数，可以求线性筛的同时求出。

莫比乌斯函数的性质

• 性质1： \[ \sum\limits_{d|n}\mu (d)=\begin{cases} 1 & n=1 \\ 0 & n\neq 1 \end{cases} \] 也就是说，\(\sum_{d|n}\mu(d)=\varepsilon(n)\)，即 \(\mu * 1=\varepsilon\)

  • 引理：\([gcd(i,j)=1]=\sum\limits_{d|gcd(i,j)}\mu(d)\)

• 性质2： \[ \varphi * 1=\operatorname{id} \] 两边同时卷 \(\mu\) 可得到 \(\varphi=\operatorname{id}*\mu\)

莫比乌斯变换与反演

设 \(f(n),g(n)\) 是两个数论函数。

• 如果有 \(f(n)=\sum_{d|n}g(d)\)，那么有 \(g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\)

  这种形式下，\(f(n)\) 称作 \(g(n)\) 的莫比乌斯变换，\(g(n)\) 称作 \(f(n)\) 的莫比乌斯反演。

• 如果有 \(f(n)=\sum_{n|d}g(d)\)，那么有 \(g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)\)

应用

莫反常常与数论分块+前缀和结合，加速运算。