唔姆~于是今天来讲莫比乌斯反演~
莫比乌斯反演又称懵逼钨丝反演，是一种让人一看就一脸懵逼的算法
为了让大家不再懵逼，今天我来换一种讲法，一种不同于大部分参考书和博客的讲法，来介绍这个莫比乌斯反演
备注：如果你对狄利克雷卷积表示的方法并不熟悉，推荐你在纸上把卷积转化成sigma的形式来看，这样也可以增强你对狄利克雷卷积的理解
备注++：想真正学好这个算法，请认真在纸上把没有一遍看懂的地方推导一遍，确保每个式子都看明白了再继续
Part I 前置技能
积性函数
首先，我们定义整数集合上的数论函数：定义域和值域都在整数集合中的函数称为“数论函数”
（真正的数论函数定义有所不同，可以自行参考维基）
那么积性函数就是这样的一类数论函数：
若函数$f$是积性函数，那么对于任意$gcdleft(i,j ight)=1$，有$fleft(ij ight)=fleft(i ight)ast fleft(j ight)$
如果函数$f$在$gcdleft(i,j ight) eq1$时也满足后面的条件，称函数$f$为完全积性函数
常见的积性函数：
$muleft(i ight)$，莫比乌斯函数
$varphileft(i ight)$，欧拉函数
$dleft(i ight)$，约数个数函数
$sigmaleft(i ight)$，约数和函数
常见的完全积性函数（注意完全积性函数一定是积性函数）
$Ileft(i ight)=1$，常函数
$varepsilonleft(i ight)=left[i=1 ight]$，单位函数
$idleft(i ight)=i$，恒等函数
狄利克雷卷积
嗯……这个东西，是今天我要讲的大部分东西的基础
那么狄利克雷卷积就是两个数论函数，通过一定的方法相乘：
定义$left(gast f ight)left(i ight)=F$，我们称F函数是g和f函数关于i的狄利克雷卷积
F的计算方式如下：
$Fleft(i ight)=sum_{d|i}gleft(d ight)fleft(frac id ight)$
还是比较好理解的吧？
狄利克雷卷积满足交换律、结合律，并且有一些经典的结论：
$left(muast I ight)=varepsilon$
$left(varphiast I ight)=id$
$left(muast id ight)=varphi$
$left(Iast I ight)=d$
$left(Iast id ight)=sigma$
其中前面三个，在莫比乌斯反演以及杜教筛中的应用很广泛，后面两个在解决大部分积性函数题目时候也有很大的作用
Part II 莫比乌斯函数/莫比乌斯反演
莫比乌斯函数
前面已经提到过这个东西......名字听起来很高大上对不对~
实际上它的定义不是特别高大上
定义莫比乌斯函数$mu$
当$i=1$时，$muleft(i ight)=1$
当$i=prod_{i=1}^{n}p_i^1$，其中$p_i$是互不相同的质数时，$muleft(i ight)=left(-1 ight)^n$
其余时候$muleft(i ight)=0$
$mu$函数的两个最重要的性质，在上文中都已经用狄利克雷卷积的形式写过了
莫比乌斯函数同时也是接下来的莫比乌斯反演的主角
莫比乌斯反演
莫比乌斯反演是一个数论反演。当初发明它的主要目的是为了简化计算（1718世纪的时候）
它的原理基于这条式子：
$left(muast I ight)=varepsilon$
我们来看一个莫比乌斯反演的实例：
设$f=left(gast I ight)$
两边同时卷积一个$mu$，变成
$fastmu=gast Iastmu$
$fastmu=gastvarepsilon=g$
莫比乌斯反演就完成了
如果写成sigma的形式就是这样的：
如果
$fleft(d ight)=sum_{i|d}gleft(i ight)$
那么
$gleft(d ight)=sum_{i|d}fleft(i ight)muleft(frac di ight)$
这是一种形式
还有一种形式是这样的：
如果
$fleft(d ight)=sum_{d|i}gleft(i ight)$
那么
$gleft(i ight)=sum_{i|d}fleft(d ight)muleft(frac di ight)$
好像在大部分莫比乌斯反演题目中后面再这一种形式更常见一些
可以把他们两个理解为“对一个东西的所有约数求和”以及“对一个东西的所有倍数求和”然后反演
详细的纯理论证明可以参考这里：https://oi-wiki.org/math/mobius/
为了加深理解，我们先来看一个例子：HDU1695
注意这里面就是把一个不太好求的东西求了一个和，然后变成了一个很好求的东西，再通过反演把它反向算出来
再来看下一个例子：求
$sum_{i=1}^{n}sum_{j=1}^{m}gcdleft(i,j ight)$
我们做一步变形，一步非常重要的变形：把$gcdleft(i,j ight)$的值提出来，变成：
$sum_{d=1}^{n}dsum_{i=1}^{n}sum_{j=1}^{m}left[gcdleft(i,j ight)=d ight]$
这一步非常重要，一定要好好理解再继续，因为它是一个超级常用的技巧
下一步，发现后面$gcdleft(i,j ight)=d$这里的$d$很烦呐，把它除上去：
$sum_{d=1}^{n}dsum_{i=1}^{frac nd}sum_{j=1}^{frac md}left[gcdleft(i,j ight)=1 ight]$
看到了吗？这就完成了向HDU1695的转变，后面就反演一下，变成这个形式：
$sum_{d=1}^{n}dsum_{i=1}^{n}muleft(i ight)frac n{id}frac m{id}$
设$D=id$，我们先枚举D再枚举D的约数d，变成这个形式
$sum_{D=1}^{N}sum_{d|D}dmuleft(frac Dd ight)frac n{id}frac m{id}$
最后面两项提到前面去，变成
$sum_{D=1}^{N}frac n{D}frac m{D}sum_{d|D}dmuleft(frac Dd ight)$
发现后面的是一个卷积的形式，就是$left(muast id ight)=varphi$
所以得到最终结果：
$sum_{D=1}^{N}frac n{D}frac m{D}varphileft(D ight)$
然后数论分块技巧，在$Oleft(sqrt n ight)$下解决
关于更多莫比乌斯反演的题目，可以看：
Part III 杜教筛
基本而言，杜教筛解决的是这样的一类问题：
对于一个积性函数$f$，求它的前缀和$sum_{i=1}^{n}fleft(i ight)$
别急，我知道你会线性筛，所以n<=10^10
显然线性时间复杂度的算法就解决不了了
但是杜教非常厉害，他发明了一个利用卷积的方法，强行把求前缀和的算法优化到了$Oleft(n^frac{2}{3} ight)$
下面我们就来看看杜教是怎么实现这个过程的
我们设$Sleft(n ight)=sum_{i=1}^{n}fleft(i ight)$，其中$f$是一个积性函数
我们再设一个积性函数$g$，并让它和$f$卷积后求前缀和，就是：
$sum_{i=1}^{n}left(gast f ight)left(i ight)=sum_{i=1}^{n}sum_{d|i}gleft(d ight)fleft(frac id ight)$
把$gleft(d ight)$提出来，先枚举$d$再枚举$d$的倍数$i$，变成：
$sum_{d=1}^{n}gleft(d ight)sum_{d|i}fleft(frac id ight)=sum_{d=1}^{n}gleft(d ight)sum_{i=1}^{frac nd}fleft(i ight)=sum_{d=1}^{n}gleft(d ight)Sleft(frac nd ight)$
上面这个东西就是积性函数$g$和$f$卷积后求出来的前缀和
恒等变形一下，我们有这个式子：
$gleft(1 ight)Sleft(n ight)=sum_{i=1}^{n}gleft(i ight)Sleft(frac nd ight)-sum_{i=2}^{n}gleft(i ight)Sleft(frac nd ight)$
等号右边的第一坨东西我们化成卷积的形式：
$gleft(1 ight)Sleft(n ight)=sum_{i=1}^{n}left(gast f ight)left(i ight)-sum_{i=2}^{n}gleft(i ight)Sleft(frac ni ight)$
如果狄利克雷卷积的前缀和非常好算的话（比如化成了$sum_{i=1}^{n}i$这样的），就可以$Oleft(1 ight)$求出来，然后记忆化搜索了
但是这样有一个问题：我一直往下记忆化，效率不还是$Oleft(n ight)$的吗？
的确，但是我们有一个好东西叫做线性筛
假设我们把一部分的$f$先筛出来，然后再把这一部分的$S$求出来，到了比某一个范围小的时候不就可以$Oleft(1 ight)$返回了吗？
根据杜教的证明（因为这东西太复杂了......懒得写上来，记住就好），当我们筛出来$Oleft(n^frac{2}{3} ight)$个$S$，剩下的记忆化时，我们的记忆化搜索时间效率降到$Oleft(n^frac{2}{3} ight)$
因此总的时间效率就是$Oleft(n^frac{2}{3} ight)$
为了加深理解，我们看一道例题：
这里就是一个选取$g$函数的很好的例子
另外一个例子：BZOJ4916
很多时候杜教筛会和莫比乌斯反演结合应用，也就是先反演出来，然后杜教筛一个和$mu$有关的积性函数（不一定是$mu$），以达成数论分块的目的
总结
杜教筛以及莫比乌斯反演的内容其实到这里就结束了，因为它们俩本身的知识性内容也不多，但是一定要确保自己理解了上面写的每一句话、每一个公式
八道例题也最好都看一遍，因为这些都是经典的以及常用的方法在题目中的体现
最后，想要学好数论方面的知识是比较难的，因为数论中的内容错综复杂，一个知识点往往和数个知识点之间有连接关系
但是学好数论必不可少的、也是方便快捷的一条路，就是认真推导
把每一个式子都在纸上写出来、理解它为什么能这么推、还有为什么要这么推
遇到题目的时候也要想一想：出题人想让我往哪个方向推导？我应该用什么方法靠近这个方向？
这样，学习数论的时候才不会感觉到无所适从，才能掌握信息竞赛中数论题目的精髓所在