莫比乌斯反演入门以及简单例题讲解

发布于 2022-11-20  603 次阅读


在学习莫比乌斯反演之前,需要了解一些前置知识:

整除分块,狄利克雷卷积。

莫比乌斯函数

记作\(\mu(n)\),定义如下:

莫比乌斯函数定义

其实这个不用太深入理解,莫比乌斯反演的重点其实在于和式的推导和函数的变换,只需要知道这个\(\mu\)函数是可以用杜教筛\(O(n^{\frac{2}{3}})\)预处理出来的就行了,当数据较小的时候可以线性筛。

很多关于gcd的和式都可以转换成含\(\mu\)的简单形式。

莫比乌斯反演

反演说白了就是对和式的变换,然后用\(\mu\)去表示一些东西。

性质

介绍两个十分重要的性质,用于反演。

1.对于任意正整数 $n\),\(\sum\limits_{d|n}\mu(d)=[n=1]$。后面这是一个真值表达式,意思是n=1为真时值为1,其余情况都为0。联想一下,是不是有一个式子和这个很对应,没错就是\([gcd(x, y) = 1]\)。

划重点,结论出现了!如下,后面的gcd一般都用这个替换掉。

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

2.对于任意正整数\(n\),$\sum\limits_{d|n}\frac{\mu(d)}{d} = \frac{\phi(n)}{n}$,在一些特殊的式子里可以用\(\phi\)替换\(\mu\)。

和式变换规则

第一种:函数体不变的的变换

$$ \sum\limits_{i=1}^{n} \sum\limits_{d|i, d|n} \mu(d) = \sum\limits_{d|n} \mu(d) \sum\limits_{i=1}^{\lfloor n/d \rfloor} $$

解释一下,因为\(i\)原本是\(d\)的倍数,\(d\)提前之后,\(i\)的有效取值就只有$\lfloor n/d \rfloor$个了,因为这后面并没有关于i的函数,所以可以直接换,如果有关于\(\)的函数的话,可以参考下面这种方法来换。

第二种:函数体需要变化的和式变换

对于下面这个式子,我们一步一步来变换。

$$ \sum\limits_{i=1}^{n} \sum\limits_{d|i, d|n} i ^ 2 * \mu(d)$$

首先明确我们的目标,是把\(\mu(d)\)提到外面去,但是第二个求和的限制有一个\(d|i\)就挺烦人的,不妨设\(i = j * d, (j 为大于0的整数)\),这是合理的,因为第二个求和符号限制了\(d\)是\(i\)的因子,那么i就可以写成\(jd\)的形式。因此,\(d|i \iff d|jd\)相当于是赘余符号,可以不写,接下来只需要通过\(i = j * d\)的规则,相应的将和式限制和函数体中的\(i\)换成\(jd\)。

$$ \sum\limits_{i=1}^{i=n} \iff \sum\limits_{jd=1}^{jd=n} \iff \sum\limits_{j=1}^{j=\lfloor n/d \rfloor} $$

注意前面提到了\(j\)是正整数,所以\(j=0\)是没有意义的,所以这里\(j\)下限为\(1\)。

函数体里面的\(i^2\)就应该换成\((j * d) ^ 2\),整理如下:

$$ \sum\limits_{d|n}\mu(d)\sum\limits_{j=1}^{j=\lfloor \frac{n}{d} \rfloor} j^2 * d ^ 2 $$

此时我们发现柿子中已经没有\(i\)了,为了方便处理,我们再将\(j\)用\(i\)表示,这一次变换只是单纯地换“变量名”,并没有数学意义上的变换,从而得到以下的柿子。

$$ \sum\limits_{d|n} \mu(d) \sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}i^2 * d ^ 2 $$

第三种:有两个和式(变量)在前面的变换

例如下面这个柿子:

$$ \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d|i, d|j}i * j * \mu(d)$$

变换方法与第二种类似,这里\(i\)和\(j\)也是做类似的变换,并且可以分开,这里需要注意将\(d\)提前之后

\(d\)的取值,应该是从\(1\)到\(min(n, m)\)。

在变换之前\(d = gcd(i, j)\),而\(1 \le i \le n, 1 \le j \le m\),所以\(1\le d \le min(n, m)\)。

$$ \sum\limits_{d=1}^{min(n, m)} \mu(d) * d^2 \sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor} i \sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}j $$

又发现这个和柿(其实是一个等差数列)是可以直接计算的:

$$ 令f(n) = \sum\limits_{i=1}^{n}i = \frac{n * (n + 1)}{2} $$

上面的柿子可以进一步化成:

$$ \sum\limits_{d=1}^{min(n, m)} \mu(d) * d^2 * f(\lfloor \frac{n}{d}\rfloor) * f(\lfloor \frac{m}{d} \rfloor) $$

有朋友可能会说,这个复杂度还是很高,每次询问都要\(O(min(n, m))\),实际做法会用杜教筛+线性筛优化预处理出\(\mu\)的前缀和,因为\(\lfloor \frac{n}{d}\rfloor\)和\(\lfloor \frac{m}{d}\rfloor\)的取值种类数较少,所以可以用二维整除分块进行优化。

比较优秀的筛法和莫比乌斯和欧拉函数前缀和模板

模板如下:

//P4213 【模板】杜教筛(Sum)
#include 
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
//杜教筛+线性筛优化,复杂度O(N^(2/3))
int mu[maxn], phi[maxn], prefix_phi[maxn], prefix_mu[maxn];
map mp_mu, mp_phi;

void init(int N = maxn - 1)//N = maxn - 1
{
    bitset vis;
    vector prim(N + 5);
    phi[1] = mu[1] = 1;
    for(int i = 2, k = 0; i <= N; ++ i)
    {
        if(!vis[i])prim[++ k]=i, mu[i] = -1, phi[i] = i - 1;
        
        for(int j = 1; j <= k && prim[j] * i <= N; ++ j)
        {
            vis[i * prim[j]] = 1;

            if(i % prim[j] == 0)
            {
                phi[i * prim[j]] = phi[i] * prim[j];
                break;
            }
            else mu[i * prim[j]] = -mu[i], phi[i * prim[j]] = phi[i] * (prim[j] - 1);
        }
    }
    for(int i = 1;i <= N; ++ i)//前缀和部分
    {
    	prefix_mu[i] = prefix_mu[i - 1] + mu[i];
    	prefix_phi[i] = prefix_phi[i - 1] + phi[i];
    }
}

int getprefix_mu(int n)//返回莫比乌斯函数的前缀和
{
	if(n < maxn) return prefix_mu[n];
	if(mp_mu.count(n)) return mp_mu[n];
	int res = 1;
	for(int l = 2, r; l <= n;l = r + 1)
	{
		r = n / (n / l);
		res -= (r - l + 1) * getprefix_mu(n / l);
	}
	return mp_mu[n] = res;
}

int getprefix_phi(int n)//返回欧拉函数前缀和
{
    if(n < maxn)return prefix_phi[n];
    if(mp_phi.count(n))return mp_phi[n];
    int res = n * (n + 1)/2;
    for(int l = 2, r; l <= n;l = r + 1)
    {
        r = n / (n / l);
        res -= (r - l + 1) * getprefix_phi(n / l);
    }
    return mp_phi[n] = res;
}

signed main()
{
	int T;scanf("%lld", &T);
	init();
	while(T --)
	{
		int n;scanf("%lld", &n);
		printf("%lld %lld\n", getprefix_phi(n), getprefix_mu(n));
	}	
}

用法就不赘述了。接下来看几个题吧。

例题

例题1:P3455 [POI2007]ZAP-Queries

这题要求的是下面这个式子:

$$\sum\limits_{x=1}^{a}\sum\limits_{y=1}^{b}[gcd(x, y) = d]$$

首先将\(x\)和\(y\)都除以一个\(d\),此时gcd会变为1。

$$\sum\limits_{x=1}^{\lfloor\frac{a}{d} \rfloor}\sum\limits_{y=1}^{\lfloor\frac{b}{d}\rfloor}[gcd(x, y) = 1]$$

用莫比乌斯反演得到(因为题目里有\(d\)了,所以我们新增一个变量\(p\)表示\(gcd(x, y)\)的因子):

$$\sum\limits_{x=1}^{\lfloor\frac{a}{d} \rfloor}\sum\limits_{y=1}^{\lfloor\frac{b}{d}\rfloor}\sum\limits_{p|gcd(x, y)}\mu(p)$$

现在将\(\mu(p)\)提到外面去:

$$\sum\limits_{p=1}^{\lfloor \frac{min(a, b)}{d} \rfloor} \mu(p)\sum\limits_{x=1}^{\lfloor\frac{a}{pd}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{b}{pd} \rfloor}$$

继续转化:

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

现在就可以做了,用杜教筛筛出\(\mu\)的前缀和,然后再整除分块即可。

代码如下:

//P4213 【模板】杜教筛(Sum)
#include 
#define int long long
using namespace std;
const int maxn = 5e4 + 9;
//杜教筛+线性筛优化,复杂度O(N^(2/3))
int mu[maxn], phi[maxn], prefix_phi[maxn], prefix_mu[maxn];
map mp_mu, mp_phi;

void init(int N = maxn - 1)//N = maxn - 1
{
    bitset vis;
    vector prim(N + 5);
    phi[1] = mu[1] = 1;
    for(int i = 2, k = 0; i <= N; ++ i)
    {
        if(!vis[i])prim[++ k]=i, mu[i] = -1, phi[i] = i - 1;
        
        for(int j = 1; j <= k && prim[j] * i <= N; ++ j)
        {
            vis[i * prim[j]] = 1;

            if(i % prim[j] == 0)
            {
                phi[i * prim[j]] = phi[i] * prim[j];
                break;
            }
            else mu[i * prim[j]] = -mu[i], phi[i * prim[j]] = phi[i] * (prim[j] - 1);
        }
    }
    for(int i = 1;i <= N; ++ i)//前缀和部分
    {
    	prefix_mu[i] = prefix_mu[i - 1] + mu[i];
    	prefix_phi[i] = prefix_phi[i - 1] + phi[i];
    }
}

int getprefix_mu(int n)//返回莫比乌斯函数的前缀和
{
	if(n < maxn) return prefix_mu[n];
	if(mp_mu.count(n)) return mp_mu[n];
	int res = 1;
	for(int l = 2, r; l <= n;l = r + 1)
	{
		r = n / (n / l);
		res -= (r - l + 1) * getprefix_mu(n / l);
	}
	return mp_mu[n] = res;
}

int getprefix_phi(int n)//返回欧拉函数前缀和
{
    if(n < maxn)return prefix_phi[n];
    if(mp_phi.count(n))return mp_phi[n];
    int res = n * (n + 1)/2;
    for(int l = 2, r; l <= n;l = r + 1)
    {
        r = n / (n / l);
        res -= (r - l + 1) * getprefix_phi(n / l);
    }
    return mp_phi[n] = res;
}

signed main()
{
	int T;scanf("%lld", &T);
	init();
	while(T --)
	{
		int a, b, d;scanf("%lld %lld %lld", &a, &b, &d);
		
		int ans = 0;
		for(int l = 1, r;l <= a / d && l <= b / d; l = r + 1)
		{
			int n1 = a / d, n2 = b / d;
			r = min(n1 / (n1 / l), n2 / (n2 / l));
			
			ans += (getprefix_mu(r) - getprefix_mu(l - 1)) * (n1 / l) * (n2 / l);
			
		}
		printf("%lld\n", ans);
		
	}	
	return 0;
}

来一道稍微难点的。

例题2:P2257 YY的GCD

不难分析所求如下:

$$
\sum\limits_{x=1}^{N}
\sum\limits_{y=1}^{M}
[gcd(x, y) \in prim]
$$

现在枚举质数\(p\):

$$
\sum\limits_{p=1}^{min(N, M)}
\sum\limits_{x=1}^{\lfloor \frac{N}{p} \rfloor}
\sum\limits_{y=1}^{\lfloor \frac{M}{p} \rfloor}
[gcd(x, y) = 1]
$$

将\(gcd\)用\(\mu\)换掉:

$$
\sum\limits_{p=1}^{min(N, M)}
\sum\limits_{x=1}^{\lfloor \frac{N}{p} \rfloor}
\sum\limits_{y=1}^{\lfloor \frac{M}{p} \rfloor}
\sum\limits_{d|gcd(x, y)}\mu(d)
$$

将\(\mu(d)\)移到前面:

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

令\(T = pd\)替换:

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

现在就可以做了,设函数

$$
f(T) = \sum\limits_{p|T, p\in prim}\mu(\frac{T}{p})
$$

答案就变成下面这个柿子:

$$
\sum\limits_{T=1}^{min(N, M)}
f(T)
\lfloor \frac{N}{T} \rfloor
\lfloor \frac{M}{T} \rfloor
$$

典型的二维整除分块。

//P2257 YY的GCD
//P4213 【模板】杜教筛(Sum)
#include 
#define int long long
using namespace std;
const int maxn = 1e7 + 9;
int mu[maxn], sum[maxn];

void init(int N = maxn - 1)
{
	bitset vis;
	vector prim(N + 5);
	vis[0] = vis[1] = true;
	mu[1] = true;
	int k = 0;
	for(int i = 2;i <= N; ++ i)
	{
		if(!vis[i])mu[i] = -1, prim[++ k] = i;
		
		for(int j = 1;j <= k && prim[j] * i <= N; ++ j)
		{
			vis[i * prim[j]] = true;
			if(i % prim[j] == 0)break;
			
			mu[i * prim[j]] = -mu[i];
		}
	}
	for(int i = 1;i <= N; ++ i)//p = i
	{
		if(vis[i])continue;//T = j
		for(int j = i;j <= N; j += i)sum[j] += mu[j / i];
	}
	
	for(int i = 1;i <= N; ++ i)sum[i] += sum[i - 1]; 
	
}


signed main()
{
	int T;scanf("%lld", &T);
	init();
	while(T --)
	{
		int n, m;scanf("%lld %lld", &n, &m);
		int ans = 0;
		
		for(int l = 1, r; l <= n && l <= m;l = r + 1)
		{
			r = min(n / (n / l), m / (m / l));
			ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
		}
		printf("%lld\n", ans);
	}	
	return 0;
}