莫比乌斯反演

本来还打算写容斥的,结果不知不觉就过(颓)了好几个月,发现原来容斥如此高妙啊QAQ,那就讲讲比较套路的反演吧。。。

莫比乌斯反演。。。听起来很高明,实际上不算太难吧(逃

首先说他是莫比乌斯反演,总要有个缘由吧。个人感觉就是因为莫比乌斯函数,μ,是他的精髓所在。

先说说μ的定义

  • n为无平方因子数且n的标准分解中有偶数个质数,μ(n) = 1;
  • n为无平方因子数且n的标准分解中有奇数个质数,μ(n) = -1;
  • n为有平方因子数时,μ(n) = 0。

 

  • μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
  • μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
  • μ(n) = 0 if n has a squared prime factor.

source: Wikipedia(En)

看到这个定义,大家想必会非常奇怪——这种sb的定义是谁想出来的,一点也不优美!

但是,大家且和我看看别处:

狄利克雷卷积

(不得不吐槽,wordpress真的好菜菜啊,不能用LaTeX,只能靠截图,不然这篇博客好打多了)

又是定义

TIM截图20180712174346.png

其中,fg为数论函数(定义域为R,值域为C的函数),* 代表的就是狄利克雷卷积。

不难看出,在狄利克雷卷积的意义下,单位元为函数:TIM截图20180712175524.png

另参见:Dirichlet convolution

看到单位元,很自然的便想到逆元。在乘法意义下,最特殊的数莫过于是1了,它的乘法逆元就是它本身。那我们合不考虑在狄利克雷卷积的意义下 1 函数(函数值恒为1)的逆元呢?

不难猜出发现这个函数就是莫比乌斯函数

证明过程(太懒了,不想打公式了233)

那这个性质就可以写成一个求和(卷积)的形式

TIM截图20180713193453

这个性质在推式子的时候非常有用。

 

有了以上知识,莫比乌斯反演就呼之欲出了。

 

莫比乌斯反演

和大多数反演(反演好多啊。。。以后应该还会专门写这样的博客吧好一个flag)一样,莫比乌斯反演就是在一种卷积的意义下通过已知量关于未知量的表达式来求得未知量的方法。

考虑以下问题:

已知 ,且 f * 1 = g ,

我们可以先回忆一下当这种卷积是各个情况时,我们会怎么做:

  1. 加法,如 x+3=5 我们通常在等式两边同时减去3
  2. 乘法,如 3×x=6 我们通常在等式两边同时除以3
  3. 模意义乘法,如 3×x=1(mod 2) 我们通常在等式两边同时乘以1
  4. ……

看到这儿,大概也就有了眉目:在一种卷积意义下,只要在等式的两边同时卷上该卷积意义下与x做卷积的数的逆元,就可以得到答案辣!

那么,我们是不是只要在等式两边同时卷上μ就稳了啊?

TIM截图20180713204316.png

这就是传说中的莫比乌斯反演了啊。。。是不是很好理解啊233

 

那么这篇博客就先到这里了啊,还有一些技巧一类的东西就以后在写题目题解的时候写吧!

 

顺便,之后更新的时候会把自己之前做给同学上课用的ppt发上来啊,敬请期待吧

(感慨一句,一万年之后终于写了博客了啊啊啊)

发表评论

电子邮件地址不会被公开。 必填项已用*标注