莫比乌斯反演
莫比乌斯反演是OI中应对数论问题的一大杀器,可以把很多以前需要脑子想的问题无脑化,把很多脑子想不通的问题机械化,非常方便。
狄利克雷卷积
对于函数,定义它们的狄利克雷卷积
为:
性质
积性
若为积性函数,那么
继承它们的积性。
证明:令为互素正整数,则易证
的全体约数可以不重不漏地表示为
。
因此:
交换律
证明:由于约数是成对出现的,显然。
结合律
证明:我们需要稍微改变一下下标的写法,然后就非常清楚了:
得证。
单位元
定义
推论
关于狄利克雷卷积我们有两条非常重要的推论:
证明:我们先证明第一条,假设有
个素因子,从当中挑去若干个相乘组成
的不含平方素因子的约数(如果约数含平方素因子则约数的
为
,可以直接忽略)则我们有:
对于第二条推论,我们将其展开:
莫比乌斯反演
定理:当且仅当
。
证明:本质上是狄利克雷卷积的推论的推论,先正着来一轮,两边同时乘以:
虽然存在这个莫比乌斯反演定理,但是我们更多的时候还是习惯逆用狄利克雷卷积的那两个推论。
示例:![\varphi(n)](#svgView(viewBox(-0.16,-13996.10,36.58,17.93)))
此时我们使用推论:
- 把式子写下来
- 用
或者
修饰
- 逆用狄利克雷卷积的推论,把求和式后面反演成卷积形式
- 通过算贡献的方式设法把
的求和项连带着只和
有关的函数值一起拖到最前面
- 化简后半部分
这一路下来其实是非常套路的,但往往效果拔群。
示例:![\sum_{i = 1}^n \varphi(i)](#svgView(viewBox(-0.01,-13387.36,74.72,19.58)))
以下为了方便起见,如果出现,皆假设
!
我们试试看刚刚学到的套路,来反演欧拉函数的前缀和:
示例:![\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = 1]](#svgView(viewBox(-0.01,-12910.73,186.57,22.03)))
这个式子对应POJ3090,即有一个个格点,问从最左下角能够看到几个格点,我们发现如果格点
不互素的话,它一定不会被看到,因此题目就被转化成了我们要求的式子,常规做法是通过把格点劈成三角形,进行转化得到答案为
,但是这毕竟还需要一点智商,而如果你莫比乌斯反演熟练的话,这个东西推起来是非常机械化的:
示例:![\sum_{i = 1}^n \sum_{j = 1}^m \gcd(i, j)](#svgView(viewBox(-0.01,-12018.24,149.11,22.03)))
观察这个式子,我们发现和上面实例中式子的唯一不同就是我们把换成了
,对应下来就是
换成了
,因此我们可以得到: