莫比乌斯反演常用于解决计数类题目(如两个$\sum$或者$\prod $….)而且大多和$\gcd$有关。
莫比乌斯函数
定义
莫比乌斯函数 $\mu(n)$ ，设$n=p_1^{k1}·p_2^{k2}·····p_m^{km}$，则有：
$$
\mu(n)=
\left{\begin{matrix}
1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n=1\
(-1)^m \ \ \ \ \ \ \prod _{i=1}^{i=m}k_i \
0 \ \ \ {\rm otherwise}(k_i>1)
\end{matrix}\right.
$$
性质
- 莫比乌斯函数是积性函数，即$\mu(a·b)=\mu(a)·\mu(b)，(\gcd(a,b)=1)$
- 根据上面性质，我们可以采取线性筛法，用 O(n)O(n) 的时间预处理出所有 $[1, n]$ 内的莫比乌斯函数值。
- $\sum_{d|n}{\mu(d)}=[n=1]$，即只有当且仅当n=1时，上式子才为1，反之为0。
- $\sum_{d|n}{\frac{\mu(d)}{d}}=\frac {\phi (n)}{n}$
莫比乌斯反演
一般形式
如果 ${\rm f(n)},{\rm g(n)}$ 是数论函数，且满足：
$$
f(d)=\sum_{d|n}g(n)
$$
则莫比乌斯反演可得：
$$
g(d)=\sum_{d|n}\mu(\frac{n}{d})f(n)
$$
等价于
$$
g(d)=\sum_{d|n}\mu(n)f(\frac{n}{d})
$$
我习惯的形式
如果 ${\rm f(n)},{\rm g(n)}$ 是数论函数，且满足：
$$
f(d)=\sum_{x=1}^{\frac{n}{d}}g(x)
$$
则莫比乌斯反演可得：
$$
g(d)=\sum_{x=1}^{\frac{n}{d}}\mu(x)f(x·d)
$$
等价于
$$
g(d)=\sum_{x=1}^{\frac{n}{d}}\mu(x·d)f(x)
$$
总结
实际上莫比乌斯反演就是利用容斥原理。
莫比乌斯反演一般有$\gcd$有关，其枚举因子和枚举倍数两种，只要搞清楚要干什么一步步推下去即可。