莫比乌斯反演学习笔记

这篇学习笔记大部分内容参考自任之洲的论文《积性函数求和的几种方法》。

0 前置知识

• 数论分块

1 一些定义

数论函数的定义

定义域为正整数域，陪域为负数域的函数被称为数论函数。

积性函数的定义

设 $f$ 为一个数论函数，若对于每一对互质的 $a,b$ 均满足 $f(ab)=f(a)f(b)$，则 $f$ 为积性函数。

特别的，设 $g$ 为一个数论函数，若对于每一对 $a,b$ 均班满足 $g(ab)=g(a)g(b)$，则 $g$ 为完全积性函数。

1.1 常见的积性函数

• 除数函数 $\sigma_k(n)$：$n$ 的所有因数的 $k$ 次方和

• 欧拉函数 $\varphi(n)$：不超过 $n$ 且与 $n$ 互质的正整数个数

• 莫比乌斯函数：

$\mu(n)=\begin{cases}1&\,n=1\\(-1)^k&\,n \text{ 为 } k \text{ 个不同的质数之积}\\ 0&\text{其它情况}\end{cases}$

1.2 常见的完全积性函数

• 单位函数：

$\epsilon(n)=\begin{cases}1&n=1\\0&n>1\end{cases}$

2 莫比乌斯反演

2.1 狄利克雷卷积

定义两个数论函数 $f(n),g(n)$ 的狄利克雷卷积为：（记作 $(f*g)(n)$）

$(f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})$

狄利克雷卷积满足以下运算定律：

• 交换律：$f*g=g*f$

• 结合律: $(f*g)*h=f*(g*h)$

• 分配律：$f*(g+h)=f*g+f*h$

• 单位元：$f*\epsilon=f$

• 若 $f,g$ 均为积性函数，则 $f*g$ 也为积性函数

2.2 莫比乌斯反演

定理 2.1. $\mu *1=\epsilon$，即：（其中函数 $1$ 为返回值恒为 $1$ 的常数函数）

$\sum\limits_{d|n}\mu(d)=\epsilon(n)$

证明

设 $n$ 有 $k$ 个不同的质因子，则

$\sum\limits_{d|n}\mu(d)=\sum\limits_{i=0}^k (-1)^i\operatorname{C}_k^i=\sum\limits_{i=0}^k \operatorname{C}_k^i(-1)^i1^{k-i}$

根据二项式定理，可得：（这里规定 $0^0=1$）

$\sum\limits_{i=0}^k \operatorname{C}_k^i(-1)^i1^{k-i}=(1-1)^k=0^k=\epsilon(n)$

所以莫比乌斯函数相当于是狄利克雷卷积下 $1$ 的逆元。

定理 2.2.

设 $f,g$ 是两个数论函数，且满足

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

则它们也满足

$g(n)=\sum\limits_{d|n} \mu(d)f(\dfrac{n}{d})$

反之亦然，即

$f=g*1\Leftrightarrow g=\mu*f$

证明

$f=g*1$

两边同时卷上 $\mu$，得：

$f*\mu=g*1*\mu$

根据定理 2.1 得：

$f*\mu=g$

两侧都卷上 $1$，得：

$f=g*1$

3 一些应用

P2257 YY的GCD

求

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)\in Prime]$

首先枚举质数 $p$，则原式可化为：

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

即

$\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(i,j)=1]$

也就是

$\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}\epsilon(\gcd(i,j)=1)$

通过定理 2.1 展开得

$\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)$

变换求和顺序，得

$\sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}[d|i]\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}[d|j]$

$\because1\sim \lfloor\dfrac{n}{p}\rfloor\text{ 中有 }\left\lfloor \dfrac{\lfloor\dfrac{n}{p}\rfloor}{d} \right\rfloor\text{个 }d\text{ 的倍数}$

$\therefore$ 得

$\sum\limits_{d=1}\mu(d)\left\lfloor \dfrac{\lfloor\dfrac{n}{p}\rfloor}{d} \right\rfloor\left\lfloor \dfrac{\lfloor\dfrac{m}{p}\rfloor}{d} \right\rfloor$

即

$\sum\limits_{d=1}^{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\lfloor\dfrac{n}{pd}\rfloor\lfloor\dfrac{m}{pd}\rfloor$

显然可以使用数论分块求解。

但是这样还不够优，考虑继续化简：

设 $T=pd$，则原式变为

$\sum\limits_{d=1}^{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}\mu(d)\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor$

也就是

$\sum\limits_{T=1}^{\min(n,m)}\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum\limits_{p\in Prime,p|T}\mu(\dfrac{T}{p})$

容易发现，最后那个求和可以预处理，最后套一下整除分块即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const long long S=1e7+1;

int n,m;
bool nop[S+5];
int tot,prime[S+5];
int mu[S+5];
long long sum[S+5];

inline int read()
{
	int s=0,w=1,ch=getchar();
	while(ch<'0'||ch>'9') ch=='-'?w=-1,ch=getchar():ch=getchar();
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s*w;
}

inline void writen(long long x)
{
	if(x>9) writen(x/10);
	putchar(x%10|48);
}

inline void init()
{
	nop[1]=true;
	mu[1]=1;
	for(register int i=2;i<=S;++i)
	{
		if(!nop[i])
		{
			prime[++tot]=i;
			mu[i]=-1;
		}
		for(register int j=1;j<=tot;++j)
		{
			if(i*prime[j]>S)
			{
				break;
			}
			nop[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=tot;++i)
	{
		for(int j=1;j*prime[i]<=S;++j)
		{
			sum[j*prime[i]]+=mu[j];	
		}
	}
	for(int i=1;i<=S;++i)
	{
		sum[i]+=sum[i-1];
	}
}

int main()
{
	init();
	int _=read();
	while(_--)
	{
		n=read();
		m=read();
		if(n>m)
		{
			swap(n,m);
		}
		long long ans=0;
		for(int l=1;l<=n;)
		{
			int r=min(n/(n/l),m/(m/l));
			ans+=(sum[r]-sum[l-1])*(n/l)*(m/l);
			l=r+1;
		}
		writen(ans);
		printf("\n");
	}
	return 0;
}

---

P2522 [HAOI2011]Problem b

求

$\sum\limits_{i=a}^b\sum\limits_{j=c}^d[\gcd(i,j)=k]$

根据容斥原理，这个柿子可以分成四块，每一块的形式都是

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k]$

即

$\sum\limits_{d=1}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\dfrac{n}{kd}\rfloor\lfloor\dfrac{m}{kd}\rfloor$

可以使用数论分块求解。

4 练习题目

P1829 [国家集训队]Crash的数字表格 / JZPTAB

P3455 [POI2007]ZAP-Queries

P3327 [SDOI2015]约数个数和

P6810 「MCOI-02」Convex Hull 凸包