莫比乌斯函数的反函数_莫比乌斯反演定理

大家好，我是知秋君，一个会写博客吟诗的知秋码农。今天说一说莫比乌斯函数的反函数_莫比乌斯反演定理,希望能够帮助大家进步!!!

这几天复习了莫比乌斯函数的运用，主要是用来解决倍数的问题的。现在就谈谈莫比乌斯函数的性质和反演定理的理解。
首先定义 $u(x)$ 为莫比乌斯函数。他有以下性质:
1. $\sum\limits_{d|m} u(x) = [m == 1]$ 其中m == 1 指m == 1 的逻辑值，也就是如果m == 1 则表达式为1 ，否则表达式为0 .上面的公式是 $u(x)$ 的定义，也就是他产生的原因。
2. $u(x)$ 是一个积性函数，也就是， $u(a*b) = u(a) * u(b)$ ; 这个可以证明的，但是没什么意思。
根据上面两个东西和素数基本定理可以知道以下求法:
1. $u(1) = 1$
2. $\sum\limits_{d|p^k}u(p^k) = 0$ . 这样推下去， $u(p) = -1 且 u(p^d) (d>1) = 0$ 。
3.根据积性和算术基本定理可知，任何一个数都是素数的乘积表示，这样的话有: $u(1) = 1 , u(p_1p_2p_3...p_r) = (-1)^r , u(x) = 0(\exists p^2_x|x)$
以上性质是有算术定理递推来的，所以可以使用晒法求出 $O(nlgn)求出来$ 。
反演定理: $g(x) = \sum\limits_{d|x}f(d) ⇒ f(x) = \sum\limits_{d|x}u(\frac{x}{d})*g(d)$ 也就是把顺序翻一下，，但是多乘一个u(x) ; 证明:
$\sum\limits_{d|x}u(\frac{x}{d})*g(d) =>$
$\sum\limits_{d|x}u(\frac{x}{d})*\sum\limits_{m|d}f(d) =>$
$令l = x / d ,且 d = am ; l = \frac{x}{am}$ 那么 $l|\frac{x}{m}$
$\sum\limits_{m|x}f(m)\sum\limits_{l|\frac{x}{m}}u(l)$
由于 $\sum\limits_{d|m} u(x) = [m == 1]$ 所以上面只有当x / m == 1时才是1，其他时候为0，那么当x = m 时，原式等于 $f(m)$ 。得证。
利用反演，可以找到倍数关系和所求数的关系，常用语gcd等题目中。以后再把例题更新上来。同时，这里总结几个求和的要点。
对于多重 $\sum$ ，要么通过贡献的思想得到直观的答案，但是也可以通过交换求和顺序得到数学上的推导答案。一下两点是求和性质：
1. $\sum\limits_{d}f(d)\sum\limits_{x和d的关系式}g(x) = \sum\limits_{d}\sum\limits_{x和d的关系式}g(x)f(d)$ 。这个很正常的，表示的意义和上面一样，但是唯一不同是合并了，运用和提取公因式的方法。乘法分配律。显然。
2.就是把1中第一个式子的顺序变化。颠倒先后顺序。写成 $\sum g(x)\sum f(d)$ 的关系，只需要把后面的量提前面就可以，一般是 $\sum f(d)$ 具有求和关系，等于一个式子或者是常量的时候，对于 $u(x)$ 肯定是把它放后面，反正原则就是把可以求出来的放到等式的最后面，因为最后面的等式是变量最少的，但是变量的限制最多的等式，由于变量少，所以可以求出来。

例题:1.hdu5656 CA Loves GCD最水的一题，就是简单的应用，可以把结果得到和N这一维无关。

莫比乌斯函数的反函数_莫比乌斯反演定理

知秋君

相关推荐