莫比乌斯反演

简介

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

符号及规定

$1.[P]$ 是指，当 $P$ 为真时，式子的值是 $1$；当 $P$ 为假时，式子的值是 $0$。
$2.a\mid b$ 是指 $b$ 被 $a$ 整除，即存在一个整数 $k$ 使得 $b=ka$。
$3.n\perp m$ 是指 $n$ 与 $m$ 互质，即 $\gcd(n,m)=1$。

积性函数

定义

如果一个数论函数 $ f(n)$ 满足：当 $ x\perp y $ 时，$f(xy)=f(x)f(y)$，则称 $f(n)$ 为 积性函数。

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数：

$$ \begin{aligned}h(x)&=f(x^p)\\ h(x)&=f^p(x)=f(x)^p\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g(\frac{x}{d})\end{aligned} $$

证明：两个积性函数的狄利克雷卷积是积性函数

已知 $h(n)=f(n)g(n)$，且 $f(n),g(n)$ 都是积性函数。
由于：若 $n\perp m$，则每个 $nm$ 的约数都可以分解成一个 $n$ 的约数和一个 $m$ 的约数的积，且若 $n\perp m,a\perp n,b\perp m$，则 $a\perp b$。
若 $n\perp m$，则

$$ \begin{aligned}h(nm) & =\sum_{d\mid nm}f(d)g\left(\frac{nm}d\right) \\ & =\sum_{a\mid n且b\mid m} f(ab)g\left(\frac{nm}{ab}\right) \\ & =\sum_{a\mid n且b\mid m}f(a)f(b)g\left(\frac na\right)g\left(\frac mb\right)\\ & = \left(\sum_{a\mid n} f(a)g\left(\frac na\right)\right)\left(\sum_{b\mid m}f(b)g\left(\frac mb\right)\right) \\ & =h(n)h(m)\end{aligned} $$

常见积性函数

欧拉函数：$\varphi(n)=\displaystyle\sum\limits_{i=1}^{n}[\gcd(i,n)=1]$，表示不大于 $n$ 且与 $n$ 互质的正整数个数。
约数个数函数：$\mathbf{d}(n)=\displaystyle\sum\limits_{d\mid n} 1=\displaystyle\sum\limits_{d=1}^{n}[d|n]$，表示 $n$ 的约数的个数。
约数和函数： $\sigma(n)=\displaystyle\sum\limits_{d|n}d=\sum\limits_{d=1}^{n}[d|n]·d$，表示 $n$ 的各个约数之和。
莫比乌斯函数

完全积性函数

元函数：$\epsilon(n)=[n=1]$
单位函数：$\mathbf{id}(n)=n,\mathbf{id}_{k}(n)=n^k$
恒等函数：$I(n)=1$

狄利克雷卷积

定义

定义两个数论函数的 狄利克雷卷积 $\ast$ ：
若 $h=f\ast g$，则

$$h(n)=\displaystyle{\sum\limits_{i|n} f(i)g(\frac{n}{i})}$$

即

$$h(n)=\displaystyle{\sum\limits_{i\times j=n} f(i) g(j)}$$

性质

$1.$ 交换律：$ \mathbf f \ast \mathbf g=\mathbf g \ast \mathbf f $
$2.$ 结合律：$(\mathbf f \ast \mathbf g)\ast \mathbf h=\mathbf f\ast(\mathbf g \ast \mathbf h) $

$$\sum\limits_{(i·j)·k=n}\Big(\mathbf f(i)\mathbf g(j)\Big)\mathbf h(k)=\sum\limits_{i·(j·k)=n}\mathbf f(i)\Big(\mathbf g(j)\mathbf h(k)\Big)$$

$3.$ 分配律：$(\mathbf f+\mathbf g)\ast \mathbf h=\mathbf f \ast \mathbf h+\mathbf g \ast \mathbf h$

$$\sum\limits_{i·j=n}\Big(\mathbf f(i)+\mathbf g(i)\Big)\ast \mathbf h(j)=\sum\limits_{i·j=n}\Big(\mathbf f(i)\mathbf h(j)+\mathbf g(i)\mathbf h(j)\Big)=\sum\limits_{i·j=n}\mathbf f(i) \mathbf h(j)+\sum\limits_{i·j=n}\mathbf g(i)\mathbf h(j)$$

$4.(x\mathbf f)\ast \mathbf g=x(\mathbf f\ast \mathbf g)$

$$\sum\limits_{i·j=n}\Big(x·\mathbf f(i)\Big)\mathbf g(j)=x·\sum\limits_{i·j=n}\mathbf f(i)\mathbf g(j)$$

$5.$单位元：$\epsilon \ast \mathbf f=\mathbf f$，其中 $\epsilon(n)=[n=1]=\begin{cases} 1 & n=1 \\ 0 & n>1\end{cases}$
$6.$逆元：对每个 $\mathbf f(1)\neq 0$ 的函数 $\mathbf f$，都存在一个函数 $\mathbf g$ 使得 $\mathbf f \ast \mathbf g=\epsilon$
如何求出一个函数的逆？
定义：

$$\mathbf g(n)=\frac 1{\mathbf f(1)}\left([n=1]-\sum_{i\mid n, i\neq1}\mathbf f(i)\mathbf g\left(\frac ni\right)\right)$$

则

$ \begin{aligned}&\quad\sum_{i\mid n}\mathbf f(i)\mathbf g\left(\frac ni\right) \\ & =\mathbf f(1)\mathbf g(n)+\sum_{i\mid n,i\neq1}\mathbf f(i)\mathbf g\left(\frac ni\right) \\ & =[n=1]\end{aligned}$

常用结论

$$ \begin{aligned}\epsilon=\mu\ast I&\Longleftrightarrow \epsilon(n)=\displaystyle\sum\limits_{d|n}\mu(d) \\ \mathbf{d}=I\ast I&\Longleftrightarrow \mathbf{d}(n)=\displaystyle\sum\limits_{d|n}1 \\ \sigma=\mathbf{id}\ast I&\Longleftrightarrow \sigma(n)=\displaystyle\sum\limits_{d|n}d \\ \varphi=\mu\ast\mathbf{id}&\Longleftrightarrow\varphi(n)=\displaystyle\sum\limits_{d|n}d·\mu(\frac{n}{d}) \end{aligned} $$

莫比乌斯函数

定义

$\mu$ 为莫比乌斯函数，定义为：

$$ \mu(n)=\begin{cases}1 & n=1 \\ (-1)^k & k\ 为 \ n\ 的不同质因子个数 \\ 0 & n\ 含有平方因子 \end{cases} $$

通俗的讲，当 $n$ 包含相等的质因子时，$\mu(n)=0$，当 $n$ 的所有质因子各不相等时，若 $n$ 有偶数个质因子，$\mu(n)=1$，若 $n$ 有奇数个质因子，$\mu(n)=-1$。

性质

莫比乌斯函数是积性函数，还有如下性质：

$$ \displaystyle\sum\limits_{d|n}\mu(d)=\begin{cases}1 & n=1\\0 & n\neq 1 \end{cases} $$

即 $\displaystyle\sum\limits_{d|n}\mu(d)=\epsilon(n)$，即 $\mu \ast I=\epsilon$
证明：
设 $n=\displaystyle\prod\limits_{i=1}^{k}p_i^{c_i},n'=\displaystyle\prod\limits_{i=1}^{k}p_i$
则$\displaystyle\sum\limits_{d|n}\mu(d)=\sum\limits_{d|n'}\mu(d)=\sum\limits_{i=0}^{k}C_{k}^{i}·1^{k-i}·(-1)^{i}=(1+(-1))^k$
根据二项式定理，易知该式在 $k=0$ 即 $n=1$ 时值为 $1$，否则为 $0$。这也同时证明了 $\displaystyle\sum\limits_{d|n}\mu(d)=[n=1]=\epsilon(n)$ 以及 $\mu\ast I=\epsilon$。

补充结论

$$[\gcd(i,j)=1]\Longleftrightarrow \displaystyle\sum\limits_{d|\gcd(i,j)}\mu(d)$$

线性筛

void get_mu()
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
}

莫比乌斯反演

定理

设 $F(n),f(n)$ 为两个数论函数，如果有：

$$F(n)=\displaystyle\sum\limits_{d|n}f(d)$$

那么有：

$$f(n)=\displaystyle\sum\limits_{d|n}\mu(d)F(\frac{n}{d})$$

证明

方法一：对原式做数论变换

$$ \begin{aligned}&\displaystyle\sum\limits_{d|n}\mu(d)F(\frac{n}{d})\\ =&\displaystyle\sum\limits_{d|n}\mu(d)\sum\limits_{k|\frac{n}{d}}f(k)\\ =&\displaystyle\sum\limits_{d|n}\displaystyle\sum\limits_{k|\frac{n}{d}}\mu(d)f(k)\\ =&\sum\limits_{kd|n}\mu(d)f(k)(k|n\ 且\ d|n才会对答案产生贡献,即\ kd|n)\\ =&\displaystyle\sum\limits_{k|n}\sum\limits_{d|\frac{n}{k}}\mu(d)f(k)\\ =&\sum\limits_{k|n}f(k)\sum\limits_{d|\frac{n}{k}}\mu(d)\\ =&f(n)\end{aligned} $$

用 $\displaystyle\sum\limits_{d|n}f(d)$ 来替换 $F(\frac{n}{d})$，再变换求和顺序。
最后一步变换的依据：$\displaystyle\sum\limits_{d|n}\mu(d)=[n=1]$，因此当 $\frac{n}{k}=1$ 时，第二个和式才为 $1$。
此时 $n=k$，故原式等价于 $\displaystyle\sum\limits_{k|n}[n=k]·f(k)=f(n)$。

方法二：利用卷积

原问题为：已知 $F=f\ast I$，证明 $f=F\ast \mu$。
易知如下转化：$F\ast \mu=f\ast I\ast\mu=f\ast \epsilon=f$。
如果 $\mathbf g=\mathbf f\ast I$，就有 $\mathbf f=\mathbf f \ast I\ast \mu=\mathbf g\ast \mu$。
也就是说，如果 $\mathbf g(n)=\displaystyle\sum\limits_{d\mid n}\mathbf f(d)$，有 $\mathbf f(n)=\displaystyle\sum\limits_{d\mid n}\mu(\frac{n}{d})\mathbf g(d)$。
类似的，可以发现 $\mathbf {id}^k$ 的逆是 $\mathbf t=\mu(n)n^k$，如果

$$\mathbf g(n)=\sum_{d\mid n}\left(\frac nd\right)^k\mathbf f(d)$$

有

$$\mathbf f(n)=\sum_{d\mid n}\mu\left(\frac nd\right)\left(\frac nd\right)^k\mathbf g(d)$$

比如，$\varphi=\mu\ast \mathbf{id}$，也就是

$$\varphi(n)=\sum_{d\mid n}\mu\left(\frac nd\right)d$$

证明 $\varphi(n)=\displaystyle\sum\limits_{d|n}d·\mu(\frac{n}{d}) $

已知 $\displaystyle\sum_{d|n}\varphi(d)=n$，表示成狄利克雷卷积的形式：$\varphi\ast I=\mathbf{id}$

$$\varphi \ast I=\mathbf{id}\Longrightarrow\varphi\ast I\ast\mu=\mathbf{id}\ast\mu\Longrightarrow \varphi\ast\epsilon=\mathbf{id}\ast \mu$$

即 $\varphi=\mathbf{id}\ast\mu\longrightarrow\varphi(n)=\displaystyle\sum\limits_{d|n}\mu(d)·\frac{n}{d}$。
上式两边同时除以 $n$，得到 $\displaystyle\frac{\varphi(n)}{n}=\displaystyle\sum\limits_{d|n}\frac{\mu(d)}{d}$。

例题

洛谷 P2257 YY的GCD

题目描述

计算

$$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}[\gcd(i,j)\in prime]$$

多组询问，每组 $N,M\leq 10^7$，数据组数 $T=10^4$。 $\gcd(i,j)=n=2(N=4,M=6)$

分析

设 $f(d)$ 为 $\gcd(i,j)=d$ 的个数，$F(n)$ 为 $\gcd(i,j)=n$ 和 $\gcd(i,j)=n$ 的倍数的个数。

$$f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m[\gcd(i,j)=d],F(n)=\sum\limits_{n\mid d}f(d)=\lfloor\frac{N}{n}\rfloor\lfloor\frac{M}{n}\rfloor$$

则

$$f(n)=\sum\limits_{n\mid d}\mu(\frac{d}{n})F(d)$$

考虑枚举所有质数 $p$：

$$\text{ans}=\sum\limits_{p\in prime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=p]=\sum\limits_{p\in prime}f(p)$$

进行莫比乌斯反演：

$$\text{ans}=\sum\limits_{p\in prime}\sum\limits_{p|d}\mu(\frac{d}{p})F(d)$$

更换枚举项，改为枚举 $\frac{d}{p}$

$$\text{ans}=\sum\limits_{p\in prime}\sum\limits_{d=1}^{\min\big(\lfloor\frac{N}{p}\rfloor,\lfloor\frac{M}{p}\rfloor\big)}\mu(d)F(dp)=\sum\limits_{p\in prime}\sum\limits_{d=1}^{\min\big(\lfloor\frac{N}{p}\rfloor,\lfloor\frac{M}{p}\rfloor\big)}\mu(d)\lfloor\frac{N}{dp}\rfloor\lfloor\frac{M}{dp}\rfloor$$

设 $T=dp$

$$\text{ans}=\sum\limits_{T=1}^{\min(N,M)}\sum\limits_{p|T,p\in prime}\mu(\lfloor \frac{T}{p}\rfloor)\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor=\sum\limits_{T=1}^{\min(N,M)}\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor\Big(\sum\limits_{p|T,p\in prime}\mu(\lfloor \frac{T}{p}\rfloor)\Big)$$

$\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor$ 可以整除分块，后面的式子可以在筛法后枚举每个质数，再枚举 $\lfloor \frac{T}{p}\rfloor$ 来统计，最后做一个前缀和即可。

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int n=10000010;
long long sum[n];
bool vis[n];
int prime[n],mu[n],g[n],cnt;
void get_mu(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
            else
                mu[i*prime[j]]=-mu[i];
        }
    }
    for(int j=1;j<=cnt;j++)
        for(int i=1;i*prime[j]<=n;i++)
            g[i*prime[j]]+=mu[i];
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+1ll*g[i];
}
int main()
{
    get_mu(10000000);
    int T;
    cin>>T;
    while(T--)
    {
        int N,M;
        scanf("%d %d",&N,&M);
        if(N>M)
            swap(N,M);
        long long ans=0;
        for(int l=1,r;l<=N;l=r+1)
        {
            r=min(N/(N/l),M/(M/l));
            ans=ans+1ll*(N/l)*(M/l)*(sum[r]-sum[l-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}