莫比乌斯反演总结

算术函数

定义

定义域为正整数、函数值为复数的函数叫算术函数，即映射。
例如：

算术函数间的运算

相加：
相乘：
狄利克雷卷积：
卷积的性质：
- 交换律：
- 结合律：
- 分配律：
- 单位元：
- 逆元：对于，使得

莫比乌斯函数与反演

定义

性质

结论1：
证明：
设为的质因子个数，为的质因子个数
令为的所有质因子之积，即若，则
当时，
当时，

推论：，

结论2（反演定理）：

若，则
若，则

即

证明：

莫比乌斯反演例题

基本套路

莫比乌斯反演题目是有转换套路的，一般只会用上述结论1，少数情况才会用结论二。

例：给定，求
分析：
首先需要把化为我们熟悉的形式。我们有，那么考虑将化为，于是，当且仅当是的倍数时才会有意义。于是又转化为。
转化后就可以带入性质1（）了，将后面的部分替换，可得到（这里为前面的值），接下来需要交换和号，即，注意到后面是可以直接计算的，其等价于的所有取值数对中均为的倍数的数对个数，所以。
我们已经得到了，莫比乌斯反演已经转化完了。接下来是计算过程，需要用到数论分块。的取值一定能分为很多块，使得每块中和都相同。这样的块一定不会超过个，对于每个块，我们直接用后面乘式的积乘块大小得到贡献，然后每次用左端点取值找右端点即可。复杂度。

总结上述基本套路：

将和式的一部分转化为的形式，并将带入
将含的部分提到前面，并重新确定枚举的约数条件（易错）
观察后面的部分，找方法将其计算出来（直接算或预处理）
进行数论分块，对于每块用直接乘每个枚举量贡献或预处理前缀和求解

预处理积性函数

基本套路中，条显然是很死板的，而灵活一些。如果后面的部分较为复杂，我们不能直接求值，那么如何计算呢？
积性函数：若数论函数满足对于所有，均有，则称作积性函数。
完全积性函数：若数论函数满足，则称作完全积性函数。
我们将后面的部分分为一个或多个积性函数，若为完全积性函数则更好。分是否为推导一下的表达式，即可用线性筛线性预处理。
例：BZOJ2820 YY的GCD

积式中的莫比乌斯反演

有时，莫比乌斯反演会存在于积式中，作为底数或指数出现。
若为底数，则可以直接反演后计算，与和式中的方法类似。
若为指数，则会较为复杂。反演后将以莫比乌斯函数为指数的部分分离出来，想办法预处理其前缀积。
例：BZOJ4816【SDOI2017】数字表格

题目汇总