浅析莫比乌斯反演

反演是对于满足$f(n)=sum_{k}a_{n,k}g(x)$的式子，我们已知$f()$求$g()$的一个过程我们称之为反演。通常来说一般的反演只能通过高斯消元来解决此类问题，但是对于对于一些特殊的反演我们可以通过一些特殊的方法来解出$g()$。例如二项式反演，莫比乌斯反演······

简单来说就是$sum lfloor {xover i} rfloor$这玩意可以在$O(sqrt n)$的复杂度内求出。

具体来说就是对于含有$lfloor {xover i} rfloor$的求和式子（$x$为常数）

对于任意一个$i(i le x)$，我们需要找到一个最大的$j(i le j le x)$，使得 $lfloor {xover i} rfloor = lfloor {xover j} rfloor$而$ j = {left lfloor { {lfloor {x over i}rfloor } over j} right rfloor} $

莫比乌斯函数是一种积性函数，其定义如下：
$$mu(d)=left{ begin{aligned} &1,&&d=0\&(-1)^k,&&d=p_1p_2cdots p_kforall p_ineq p_j \ &0,&& others\ end{aligned} right.$$ 莫比乌斯函数存在如下性质：
$$F(n)=sum_{d|n}mu(d)=left{ begin{aligned} & 1, &&n=1\ &0, && nneq0\ end{aligned} right.$$ 我们还可以补充定义单位函数$varepsilon(n)=F(n)=sum_{d|n}mu(d)$

通过莫比乌斯函数是积性函数的性质，我们可以用线性筛或者其他数论中的筛子求出莫比乌斯函数的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool vis[N];
int mu[N],pri[N],cnt=0;

void (){
    int k;
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt;j++){
            k=i*pri[j];
            if(k>N)) break;
            vis[k]=1;
            if(i%pri[j]==0){mu[k]=0;break;}
            else mu[k]-=mu[i];
        }
    }
}

由我们前文对反演的定义，我们来推导莫比乌斯反演。

我们已知函数
$$f(n)=sum_{d|n}g(d)$$ 接着我们说一句废话
$$g(n)=sum_{m|n}[{n over m}==1]g(m)$$ 由莫比乌斯函数的性质我们可以将$varepsilon(n)$带入刚才的废话方程中：
$$g(n)=sum_{m|n}varepsilon({n over m})g(m)$$ 展开得：
$$g(n)=sum_{m|n}sum_{d|{nover m}}mu(d)g(m)$$ 我们再来讨论${d|{nover m}}$,这堆东西可以化成$md|n$，所以也可以变成${m|{nover d}}$，所以上式可以化成：
$$g(n)=sum_{d|n}mu(d)sum_{m|{nover d}} g(m)$$ 然后后面这一块可以变成由$f()$来表示，故：
$$g(n)=sum_{d|n}mu(d)f({nover d})$$ 所以我们推出了莫比乌斯反演的公式就是：
$$g(n)=sum_{d|n}mu(d)f({nover d})$$

在一些题目中我们会遇到一些带有$ gcd $的反演情况，通常都是求：
$$sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==k]$$ 这样一个式子，或者是它的变形，为解决有关$ gcd $的问题我们不妨设$g(n,m)=sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==k]$，很显然这个式子可以求但是复杂度是$O(n^2logn)$的，但是这样的复杂度我们并不能接受，我们可以尝试通过反演在$O(n)$的复杂度内解决。

我们首先考虑化简这个式子：
$$f(n,m)=sum_{i=1}^{ lfloor{ n over k }rfloor }sum_{j=1}^{lfloor{m over k}rfloor}[gcd(i,j)==1]$$ 我们发现$[gcd(i,j)==1]$代入$varepsilon(n)$中再代入上式中式子的值不变，故我们将$[gcd(i,j)==1]$代入$varepsilon(n)$中再代入上式中。得：
$$f(n,m)=sum_{i=1}^{ lfloor{ n over k }rfloor }sum_{j=1}^{lfloor{m over k}rfloor}sum_{d|gcd(i,j)}mu(d)$$ 改变求和顺序得：
$$f(n,m)=sum_{d|n}^{lfloor{ min(n,m) over k }rfloor}mu(d)sum_{i=1}^{lfloor{ n over k }rfloor}d|isum_{i=1}^{lfloor{ m over k }rfloor}d|i$$ （其中$d|i$表示当满足$d$整除$i$时，对答案有$1$的贡献）整理得:
$$f(n,m)=sum_{d|n}^{lfloor{ min(n,m) over k }rfloor}mu(d){lfloor{ n over kd }rfloor}{lfloor{ m over kd }rfloor}$$