浅谈莫比乌斯反演

离散数学课讲到这一部分就停下来了,之前也是遇到很多这种数学题被虐,所以就简单整理一下。

首先谈一下积性函数,对于一个定义域为N+的函数f,对于任意两个互质的正整数a,b,均满足f(ab)=f(a)f(b),则称函数f为积性函数。若对于任意整数a,b都有f(ab)=f(a)f(b),则函数f被称为完全积性函数。

性质:
(1)对于任意积性函数f,均有f(1)=1
证明:因1与任何数都互质,假设存在一个正整数a满足f(a)!=0,故由定义:

f(a)=f(1∗a)=f(1)f(a)

因f(a)不为0,故等号两端同时消去一个f(a),得:

f(1)=1

(2)对于一个大于1的正整数N,设N=ΠPi,pi为互不相同的素数。那么对于一个积性函数f来说,有:
$$f(N)=f(\prod p_{i})=\prod f(p^{a_i})$$

若f完全积性,则:
$$f(N)=\prod f(p_i)^{a_i}$$

证明:由积性和完全积性的定义易得。

接下来介绍莫比乌斯函数u

$$f(x)=
\begin{cases}
1& \text{n=1}\
(-1)^k& \text{n=p1p2…pk}\
0& \text{else}
\end{cases}$$

性质:
(1)对于任意正整数n,有:

$$ \sum_{d|n} \mu(d) = (n == 1) $$

(2)对于任意正整数n,有:

$$ \frac{\mu(d)}{d} = \sum_{d|n} \frac{\varphi(n)}{n} $$

其中φ(n)是欧拉函数,即小于n的正整数中与n互质的个数。

接下来介绍求积性函数的通用解法,即线性筛求积性函数。

首先回顾一下埃式筛法与线性筛法。埃氏筛法就是把每一个素数的倍数标记为合数,该方法的复杂度是O(nloglogn),并不是线性。因为对于大的合数它被标记了它的素因子个数次,因此浪费了时间。线性筛法的大致思路就是:遍历每一个数i,对所有不超过 i 最小素因子的素数p,将 i∗p标记为合数。

所以我们用线性筛法求欧拉函数如下:

欧拉函数φ
考虑将所有数分成三类:
(1)质数 φ(i)=i−1
(2)最小质因子指数为1:φ(i∗p)=φ(i)φ(p)
(3)最小质因子指数大于1:φ(i∗p)=p∗φ(i)(可从欧拉函数的定义式出发)(n*连乘(1-1/pi),后面的这个不变,前面的乘上p就好)

代码:

莫比乌斯函数μ
因为线性筛每次都是用最小质因子去筛每一个数。
故也可分为三类:
(1)i为质数:μ[i]=−1
(2)i已经包含最小质因子p:μ[i∗p]=0
(3)i不包含最小质因子p :μ[i∗p]=−μ[i]
代码:

最后就是莫比乌斯的反演的内容了。

若f(n), g(n)满足如下关系,

$$f(n) = \sum_{d|n}g(d) $$

则有莫比乌斯反演:

$$g(n) = \sum_{d|n} \mu(\frac{n}{d}) f(d) = \sum_{d|n} \mu{d} f(\frac{n}{d}) $$

变形

$$ f(i) = \sum_{d=1}^{[\frac{n}{i}]}g(d\cdot i) \Rightarrow g(i) = \sum_{d=1}^{[\frac{n}{i}]} f(d \cdot i)\mu(d) $$

对于一些函数f(n),如果我们很难直接求出它的值,而容易求出倍数和或约数和F(n),那么我们可以通过莫比乌斯反演来求得f(n)的值

例:f(n)表示某一范围内(x,y)=n的数对的数量,F(n)表示某一范围内n|(x,y)的数对的数量

那么直接求f(n)并不是很好求,而F(n)求起来相对无脑一些,我们可以通过对F(n)进行莫比乌斯反演来求得f(n)。关于莫比乌斯函数的应用的计算,通常是需要分块计算的。

参考博客1博客2

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注