蒟蒻林荫小复习——莫比乌斯反演

莫比乌斯反演

积性函数：对于函数f，如果有质数p,q,使得f(p)f(q)=f(pq),则函数f为积性函数

设积性函数f，有和函数

显然，F由f决定，这种关系是否可以反过来？

 　F(1)=f(1)F(1)=f(1)      
  F(2)=f(1)+f(2)F(2)=f(1)+f(2)      
  F(3)=f(1)+f(3)F(3)=f(1)+f(3)      
  F(4)=f(1)+f(2)+f(4)F(4)=f(1)+f(2)+f(4)   
  F(5)=f(1)+f(5)F(5)=f(1)+f(5)      
  F(6)=f(1)+f(2)+f(3)+f(6)F(6)=f(1)+f(2)+f(3)+f(6)      
  F(7)=f(1)+f(7)F(7)=f(1)+f(7)    
  F(8)=f(1)+f(2)+f(4)+f(8)F(8)=f(1)+f(2)+f(4)+f(8)     

可以发现，我们可以由F去反推f

形式化的说，f(x)等于形式上一些±F(x/d)的和

则可能有这样的式子：

其中μ是算术函数，如果等式成立，则

μ(1)=1

μ(2)=-1

μ(3)=-1

μ(4)=0

μ(5)=-1

μ(6)=1

当有质数p时，f(p)=F(p)-F(1）

则我们可以发现，μ(1)=1，对于任何一个质数，μ(p)=-1

因为F(p^2)=f(1)+f(p)+(fp^2），f(p^2)=F(p^2)-F(p)

则μ(p^2)=0

这要求对于质数p有p^2=0，向下递推可知f(p^3)=F(p^3)-F(p^2)

发现，μ(1)=1,μ(p)=-1,μ(p^2)=0,μ(p^3)=0;

可知，μ(p^k)=0;

设质数p1p2p3互不相同

对于f(p1p2)=F(p1p2)-F(p1)-F(p2)+F(1)

则此时μ(p1p2)=1

对于f(p1p2p3)=F(p1p2p3)-F(p1p2)-F(p1p3)-F(p2p3)+F(p1)+F(p2)+F(p3)-F(1)

可以发现，μ(p1p2p3)=-1,μ(p1p2)=1。

同理，μ(p1p2p3p4)=1,μ(p1p2p3p4p5)=-1

则可知，对于μ(1)=1,μ(p1p2p3p4...pk)(互为不同质数)=(-1)^k

假设我们现在定义一个合数x且x的质因数分解中有相同的质数记作

x=p1pk^2

那么f(p1pk^2)=F(p1pk^2)-F(p1pk)-F(pk^2)+F(pk^2)

可以发现，μ(p1)=-1,μ(pk^2)=0,μ(p1pk^2)=0

则可以推断出，如果x的质因数分解形如x=p1p2p3p4...pk^2,则μ(x)=0

综上，证明得出莫比乌斯函数μ(x)

1. x=1时μ(x)=1


2. x的质因数分解形如x=p1p2p3p4....pk，p1p2p3p4...互不相同，则μ(x)=(-1)^k


3. 如果不属于以上两种情况，即对x进行质因数分解有重复质数，μ(x)=0


4. 莫比乌斯函数是积性函数

莫比乌斯函数的性质：

容易发现,n=1时易证，

n>1时，根据积性函数定义可知F(n)=F(P1^a1​​)F(P2^a2​​)⋯F(Pt^at​​)

其中n=p1^a1*p2^a2​...*pt^at。

则对于F(p^k)有(k>2时)

k<=2时，1+(-1)=0

因此，n>1时F(n)=0

莫比乌斯反演：

对于：

有：

另外一种形式：

对于：

有：