莫比乌斯反演

恩,上图就是大名鼎鼎的莫比乌斯环,估计大部分人听到莫比乌斯这个名字首先想到的是这个吧,不过和今天讲的Möbius inversion,即莫比乌斯反演没有多大关系,不过他们都是指的一个人,德国数学家、天文学家莫比乌斯。那下面我们就来说莫比乌斯反演了。

当初看到这个东西的时候,应该是在一本组合数学书上看到的吧,当时只见到公式非常的犀利,还在迷糊的情况下,套公式做了几个题,真是非常的囧啊。话说莫比乌斯怎么高深的名字是什么东西呢,浅显一点说,其实就是容斥原理!

容斥原理应该都很清楚的吧

假设我们要求P(A∪B∪C),但是我们现在只知道P(A),P(B),P(c),那么P(A∪B∪C)=P(A)+P(B)+P(C)-P(A∩B)-(B∩C)-P(A∩C)+P(A∩B∩C)

而莫比乌斯反演则是应用在偏序集上的容斥原理

假设:
$$g(A)=\sum_{S:S\subseteq A}f(S)$$
那么:
$$f(A)=\sum_{S:S\subseteq A}(-1)^{\mid A \mid – \mid S \mid}g(S)$$

其中|A|和|S|指的是集合里元素的个数

然后再进一步的,整除关系就是一种偏序集关系,那么对应于整除运算的莫比乌斯反演是这样的

已知
$$f(n)=\sum_{d\mid n}g(d)$$
那么
$$g(n)=\sum_{d\mid n}f(d)\mu(n/d)$$
其中mu函数就是叫莫比乌斯函数,是积性函数
$$\mu(n)=\left\{\begin{array}{ll}1 & (n=1) \\ (-1)^s & (l_1=l_2 \dots =l_s=1) \\ 0 & (\exists l_j>1,1 \leq j \leq s) \end{array} \right$$

好了,利用莫比乌斯反演我们可以很方便的求的很多东西,比如说欧拉函数,欧拉函数指小于n的和n互质的数的个数,并且,欧拉函数有一个性质

$$\sum_{d \mid n}\varphi(d)=n$$

那么f(n)=n,而g(n)就是所求的欧拉函数,那么利用莫比乌斯反演就能求得欧拉函数

$$\varphi(n)=\sum_{d \mid n}d \cdot \mu(n/d)$$

——————-我是分割线哎^o^——————————————————–

lqp18_31建议下再加点东西
证明的话感觉写起来会比较诡异,大家意会吧
说一下这个经典题目:令$$R(M,N)=1 \leq x \leq M,1 \leq y \leq N$$中 gcd(x,y)=1 的个数
我们说G(z)表示gcd(x,y)是z的倍数的个数(以后都省略$$1 \leq x \leq M,1 \leq y \leq N$$的前提),换句话说z|gcd(x,y)的个数,那么很显然$$G(z)=\lfloor M/z \rfloor * \lfloor N/z \rfloor$$,令F(z)表示gcd(x,y)=z的个数,所以$$G(z)=\sum(F(z)+F(2*z)+F(3*z)…)$$,于是我们得到$$F(z)=\sum(G(z)*\mu(z)+G(2*z)*\mu(2*z)…)$$,从而得到了我们最终的答案$$ans=\sum_{z \geq 1} \lfloor M/z \rfloor * \lfloor N/z \rfloor*\mu(z)$$

然后就是有几道练习题大家有兴趣可以做一下SPOJ4491 PGCD,SPOJ7001 VLATTICE,ZOJ3435

您可能喜欢:
我猜您可能还喜欢:
,

有 7 条《莫比乌斯反演》的回复

  1. 感觉莫比乌斯反演之所以神奇因为它的和函数为n>1时等0,n=1时等1

  2. 你可以再讲一下如何证明什么的。

    还有个很经典的问题:令R(N)= 1 \leq x,y \leq N中 gcd(x,y)=1 的个数,然后证明 R(N)=\sum_{d \geq 1} \lfloor N/d \rfloor ^ 2 \mu(d)。

  3. 虽然在围脖上乱加了你,却不知道你好厉害的……今天搜解题报告路过,膜拜下orz

发表回复