莫比乌斯反演是数论中的重要内容，在许多情况下能够简化运算。
参考资料
前言
以前曾经简单的看过Mobius反演的一些介绍，但是看的很不认真，趁着去ZR讲Mobius反演之前赶紧恶补一下qwq
前置知识和技巧
数论函数
数论函数即定义域为$N^+$的函数
积性函数
若对于任意一对正整数$a,b$,有$\gcd(a,b) = 1$,且$f(ab) = f(a) \times f(b)$,那么函数$f$称为不完全积性函数。
完全积性函数的的要求就是把$\gcd(a,b) = 1$这个条件去掉
狄利克雷卷积
我们称$(f * g)(n)$是 数论函数 $f,g$的狄利克雷卷积，那么有：
$$(f * g)(n) = \sum_{d|n} f(d) g(\frac nd)$$
性质
狄利克雷卷积运算满足交换律、结合律和分配律。
交换律： $f * g = g * f$
结合律: $f * (g * h) = (f * g) * h$
分配律：$(f + g) * h = f * h + g * h$
单位元
定义数论函数$\varepsilon(n)=[n=1]$ 为狄利克雷卷积的单位元。
$$(f * \varepsilon)(n) = (\varepsilon * f)(n) = \sum_{d|n} \varepsilon(d) f(\frac nd) = f(n)$$
从上式可以看出：在狄利克雷卷积的意义下，单位元$\varepsilon$函数就相当于在实数意义下的$1$。
引入
我们考虑求和函数：
$$F(n) = \sum_{d | n} f(d)$$
手动计算一下$n$比较小时的情况，我们可以得到$f$和$F$之间的关系：
当$n = p^2(p \in \rm{prime})$时，
$$F(p) = f(1) + f(p)$$
$$F(n) = f(1) + f(p) + f(n) = f(1) + f(p) + f(p^2)$$
那么显然,
$$f(n) = F(n) - F(p) = F(p^2) - F(p)$$
因为$\mu(p^2) = 0$,于是我们可以大胆的做出猜测：
$$(\mu * F)(n) = f(n)$$
Mobius函数
等等，那个$\mu$函数是什么意思？
$\mu$函数就是俗称的$\rm Mobius$函数，它的定义式是这个样子的：
$$\sum_{d|n} \mu(d) = [n = 1]$$
其实就是：
$$\mu * 1 = \varepsilon$$
但为了方便，我们经常以这种方式定义$\rm Mobius$函数：
求出$n$的缩系：$n = p_1^{a_1}p_2^{a_2}…p_{\varphi(n)}^{a_{\varphi(n)}}$
最后重要的一条，$\rm Mobius$函数是不完全积性函数。
Mobius反演
Mobius反演实际上就是按照$\rm Mobius$函数的性质，玄学的推出来式子啦qwq
假设有数论函数$f,g$满足：
$$f(n) = \sum_{d|n} g(d)$$
在狄利克雷卷积的意义下，实际上就是
$$f = g * 1$$
那么我们把等式两边同时卷一个$\mu$函数，得到
$$f * \mu = g * 1 * \mu$$
也就是：
$$g = f * \mu$$
把狄利克雷卷积替换成式子，展开来：
$$g(n) = \sum_{d|n} \mu(d) f(\frac nd)$$
例题
Sample Probelm #1
我们以一道例题为例，来看看Mobius反演应该如何应用.
题意就是让你求：
$$\prod_{i=1}^n \prod_{j=1}^n \frac {lcm(i,j)}{\gcd(i,j)}$$
根据小学奥数内容: $\gcd(i,j) \times lcm(i,j) = i \times j$
$$\prod_{i=1}^n \prod_{j=1}^n \frac {ij}{\gcd(i,j)^2}$$
把$\prod$符号移到分数线里面：
$$\frac {\prod_{i=1}^n \prod_{j=1}^n ij}{\prod_{i=1}^n \prod_{j=1}^n \gcd(i,j)^2}$$
把分子上的式子拆开就能得到：
$$\prod_{i=1}^n \prod_{j=1}^n ij = \prod_{i=1}^n (i^n \times n!) = (n!)^{2n}$$
这个东西非常好求，然后我们来考虑分母。
先不考虑那个$2$次方，我们看到的是这个式子：
$$\prod_{i=1}^n \prod_{j=1}^n \gcd(i,j)$$
我们枚举$gcd(i,j)$的可能性:
$$\prod_{d=1}^n \prod_{i=1}^n \prod_{j=1}^n [\gcd(i,j) = d]$$
也就是：
$$\prod_{d=1}^n d ^ {\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j) == d]}$$
然后我们同时除一下$d$
$$\prod_{d=1}^n d ^ {\sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd} [\gcd(i,j) == 1]}$$
只看指数：
$$\sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd} [\gcd(i,j) == 1]$$
这不就是LuoguP3455 ZAP吗！
现在我们才开始真正的Mobius反演！
由Mobius函数的定义式：
$$\mu * 1 = \varepsilon$$
我们把$gcd(i,j)$代入可得。
$$\sum_{d|gcd(i,j)} \mu(d) = [\gcd(i,j) = 1]$$
所以，原式可以简化为：
$$\sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd} \sum_{k|\gcd(i,j)} \mu(k)$$
我们变换枚举顺序，首先枚举$d$
$$\sum_{d=1}^n \sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd} [k|\gcd(i,j)] \cdot \mu(k)$$
同时除一下$k$:
$$\sum_{d=1}^n \mu(k) \sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd} [\gcd(i,j) \in Z]$$
显然$\gcd(i,j) \in Z$恒成立，于是我们把它去掉。
$$\sum_{k=1}^{\min(\frac nd,\frac md)} \sum_{i=1}^{\frac {n}{kd}} \sum_{j=1}^{\frac {n}{kd}} \mu(k)$$
然后根据乘法分配律，得到：
$$z = \sum_{k=1}^{\frac nd} \mu(k) \lfloor \frac {n^2}{kd}\rfloor$$
这个东西显然可以数论分块，然后我们把它带回原式计算即可。
代码就不贴了qwq
Sample Problem #2
又是一道经典题目,请读者自己按照前面的套路思考一下再看下面的题解。
我们发现，题目其实就是让求这个式子：
$$\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) \in \rm{prime}]$$
我们枚举$gcd(i,j)$的答案，质数$k$
$$\sum_{k=1}^{\min(n,m)} \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) = k] (k \in \rm{prime})$$
然后我们同时除一下k，得到：
$$\sum_{k=1}^{\min(n,m)} \sum_{i=1}^{\frac nk} \sum_{j=1}^{\frac mk} [\gcd(i,j) = 1] (k \in \rm{prime})$$
开始喜闻乐见的Mobius反演：
$$\sum_{k=1}^{\min(n,m)} \sum_{i=1}^{\frac nk} \sum_{j=1}^{\frac mk} \sum_{d|\gcd(i,j)} \mu(d)$$
变换枚举顺序：
$$\sum_{d=1}^{\min(n,m)} \sum_{k=1}^{\min(n,m)} \sum_{i=1}^{\frac nk} \sum_{j=1}^{\frac mk} [d|\gcd(i,j)] \cdot \mu(d)$$
然后我们同时除一下$d$:
$$\sum_{d=1}^{\min(n,m)} \sum_{k=1}^{\min(n,m)} \sum_{i=1}^{\frac {n}{kd}} \sum_{j=1}^{\frac {m}{kd}} [\gcd(i,j) \in Z] \cdot \mu(d)$$
显然，原式可以简化为：
$$\sum_{d=1}^{\lfloor \frac nk \rfloor} \sum_{k=1}^{n} \lfloor \frac {n}{kd}\rfloor \lfloor \frac {m}{kd}\rfloor \mu(d)$$
然后我们设$T = kd$,代入得：
$$\sum_{d=1}^{\lfloor \frac nk \rfloor} \sum_{k=1}^{n} \lfloor \frac {n}{T}\rfloor \lfloor \frac {m}{T}\rfloor \mu(d)$$
然后我们枚举一下$T$,并把它挪到前面去：
$$\sum_{T=1}^n \lfloor \frac {n}{T}\rfloor \lfloor \frac {m}{T}\rfloor \sum_{k|T,k \in prime} \mu \left( \frac Tk \right)$$
然后我们预处理一下后面的东西，最后数论分块一下，就解决问题了qwq
本题代码
1 | /* Headers */ |
总结
Mobius反演并不是多么难的算法，它更像是一种技巧，可以帮助你更方便的计算出式子
对于布尔一类的求和一般考虑用$\mu * 1 = \varepsilon$来解决
对于直接贡献的可以考虑变换枚举顺序使它变成系数。
要学会灵活的变换枚举的顺序和内容
利用积性函数的性质来用线性筛预处理，范围较大可以考虑杜教筛