莫比乌斯反演

恩,上图就是大名鼎鼎的莫比乌斯环,估计大部分人听到莫比乌斯这个名字首先想到的是这个吧,不过和今天讲的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

发表评论