(Preface)
莫比乌斯反演是一种看似高深的数学知识（所以被萌新们称作懵逼钨丝反演），可实际上有一定了解之后，就会发现也不过那点套路啦~~~
因此，本文主要是对莫比乌斯反演的相关定义以及基本套路的介绍。
前置知识
- 狄利克雷卷积： 这个东西比较简单，其实也就在一些定理证明上会派上用场，不会也罢。实在想知道的可自行百度。
- 除法分块： 这个就很有用了，是莫比乌斯反演题的常客，或许可以看看这篇博客：除法分块及其应用。
莫比乌斯函数
定义
莫比乌斯函数，符号为(mu(d))，它的具体定义如下：
唔姆，余不太用得来数学符号，上面的式子可能有些诡异。
但信（罗）仰（马）又不允许余在公式里使用中文，因此下面再放一份文字描述：
- 若(d=1)，(mu(d)=1)。（积性函数的共通性质）
- 若(d)能分解为(k)个不相同的质数的乘积，(mu(d)=(-1)^k)。
- 若(d)包含相同的质因子，(mu(d)=0)。
性质(1)：(sum_{d|n}mu(d)=[n=1])
这是一个基本性质，用狄利克雷卷积的形式表示就是：
性质(2)：(sum_{d|n}frac{mu(d)}d=frac{phi(n)}n)
这个东西其实很好证的啦，把两式同时乘上(n)，得到：
其实这东西完全可以写成狄利克雷卷积的形式，也就是：
这个东西怎么来的呢？
首先要知道(mu*I=e)（上面有了），(phi*I=id)（欧拉函数的性质，这里就不证明了），(f*e=f)（元函数的性质，其中(f)为任意函数）。
那么，只要在②式两边同时卷个(mu)，就会发现(I)刚好和它消掉了，也就得到了要证的式子。
莫比乌斯反演定理
公式
证明
考虑如何证明，同样需要狄利克雷卷积的知识。
显然这两个式子分别为：
然后就发现这一步证明和前面性质(2)的证明非常像，只要在②式两边同时卷个(I)，就得到①式啦！
是不是顿悟了？那就尽情地夸赞余吧！
补充说明
实际上吶，这个定理使用得并不多。
（但还是有的，而且用得非常妙：【BZOJ4833】[Lydsy1704月赛] 最小公倍佩尔数。）
而做莫比乌斯反演题更常见的解题方式将在下面进行介绍。
莫比乌斯反演的基本套路
例题
给出一道典型例题：【BZOJ1101】[POI2007] Zap。
唔姆，下面就来介绍一下余的做法。
套路一
考虑题目中给出的式子：
下面介绍第一个经典套路，对于(gcd(i,j))，一般做法就是枚举(gcd)。
但由于此题中已经限定(gcd(i,j)=d)（唔姆，似乎例题选得不太好？），因此无需枚举，直接将(i,j)都除以(d)，得到：
套路二
第二个套路，对于([gcd(i,j)=1])，利用(sum_{d|n}mu(d)=[n=1])这个基本性质，把它用莫比乌斯函数表示得到：
其实核心目的就是去掉带有中括号的布尔值表达式。
然后调整枚举顺序，将(p)提前得到：
实际上熟练之后这些也都可以一步完成。
最后的求解
只需要除法分块就可以了。
总结
基本步骤就是上面的两个套路啦，可以多做些板子题去体会体会。
你会发现，即便是再华丽的剧场，莫比乌斯反演在其中扮演的角色基本上也就只有这两招而已。
(Postscript)
以上就是莫比乌斯反演的基本套路了，其他一些更高级的套路余或许会在做过更多题目之后去介绍。
完结撒花。