浅谈莫比乌斯反演

那些各种各样的性质与定理,大多是前人几年甚至几十年才得出来的,哪里是你几天就能理解并证明的。

简介

莫比乌斯反演是数论中的重要内容。对于一些函数 f(n)，如果很难直接求出它的值，而容易求出其倍数和或约数和 g(n)，那么可以通过莫比乌斯反演简化运算，求得 f(n) 的值。 --OI Wiki

莫比乌斯函数

定义

令 n=\prod_{i=1}^k p_i^{c_i}，其中 p_i 为质因子，c_i\ge 1。

1. 当 n=1 时，\mu(n)=1。
2. 当 n\not = 1 时：

• 若 \exists i\in[1,k],c_i>1\mu(n)=1。
• 若 \forall i \in [1,k],c_i=1，那么 \mu(n)=(-1)^k。

性质

莫比乌斯函数是积性函数，并且有以下性质：

求法

由于莫比乌斯函数是典型的积性函数，所以也可以用欧拉筛筛出来。

I void GM(){
    RI i,j;for(mu[1]=1,i=2;i<N;i++) for(!v[i]&&(mu[p[++tot]=i]=-1,0),j=1;j<=tot&&i*p[j]<N;j++)
    if(v[i*p[j]]=1,i%p[j]) mu[i*p[j]]=-mu[i];else break ;
    for(i=1;i<N;i++) mu[i]+=mu[i-1];
}

莫比乌斯反演

为定义在非负整数域上的两个函数，且他们之间满足

。

那么我们有

这就是莫比乌斯反演定理，它还有另外一种形式：

如果

那么我们有

例题

基础题

• P2522 [HAOI2011]Problem b
• P3455 [POI2007]ZAP-Queries
• P2257 YY的GCD

提高题

咕了