莫比乌斯函数

假定有一个定义域是正整数的函数f(n),定义F(n)=sigma[f(d)],d|n(F称为f 的和函数)。

那么如果我们得到了F函数,就可以通过莫比乌斯反演公式得到f函数:f(n)=sigma[u(d)*F(n/d)],d|n

其中u是莫比乌斯函数的记号,其定义为:

u(n) = 1 n=1
  = (-1)^r n=p1*p2*......pr,其中pi为各不相同的素数
  = 0  其它

莫比乌斯函数的性质:

1)莫比乌斯函数是积性函数

2)对莫比乌斯函数进行莫比乌斯反演,得到的函数除F(1)=1外恒为0。

//若f是欧拉函数,则f(n)=n*(sigma[u(d)/d]),d|n。

原文地址:https://www.cnblogs.com/dramstadt/p/8027595.html