莫比乌斯反演学习笔记

时间：2024-02-01 14:55:48

前置：整除分块

  • 主要形式就是：

\[\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor \]

这个式子正常是 \(\Theta(n)\) 的效率，但是我们还可以缩小成 \(\Theta(\sqrt{n})\)。

  • 对于每一个 \(\lfloor\frac{n}{i}\rfloor\) ， 易得（打表）有许多的 \(\lfloor\frac{n}{i}\rfloor\) 是一样的（废话）。我们就可以根据它们的分布情况进行计算。

可以发现，对于每个相同值的一块，最后一个数是 \(\frac{n}{\frac{n}{i}}\) ，然后就可以 \(\Theta(\sqrt{n})\) 处理了。

代码

for(int l=1,r;l<=n;l=r+1){
	r=n/(n/l);
	ans+=(r-l+1)*(n/l);
}

拓展

  • 有时候，可能推出来的式子不一定就是一个很裸的整除分块，可能会与某些积性函数相乘，如： \(\mu,\phi\) ...... 这时候，每当我们使用整除分块跳过一个区间的时候，其所对应的函数值也跳过了一个区间。所以此时，就需要乘上那一个区间的函数值，利用前缀和记录即可。

莫比乌斯函数

定义

\(\mu (d)\) 为莫比乌斯函数的函数名，是一个由容斥系数所构成的函数。其定义为：
1、当 \(d = 1\) 时， \(\mu (d)=1\) 。
2、当 \(d = \prod_{i-1}^k\ p_i\) ,并且所有的 \(p_i\) 为不同的素数的时候， \(\mu(d)=(-1)^k\) 。
3、当 \(d\) 含有的任一质因子的幂大于 \(2\) 次，那么 \(\mu(d)=0\) 。

性质

1、最常用：对于任意正整数 \(n\) ，\(\sum_{d|n}\mu(d)=[n=1]\) 。其中 \([\ ]\) 代表的是布尔型，即只有 \(n=1\) 成立的时候才为 \(1\) ，其他情况为 \(0\) 。（由 \(\mu\) 的容斥系数的性质可证明。PS:我不会。）

2、对于任意正整数 \(n\) ,

\[\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n} \]

具体的证明见博客：莫比乌斯反演

代码实现

任何函数在OI中都是需要用到值的，那么我们就需要一些筛法，其中 \(xxs\) （线性筛）是最简单的一种，在线性筛素数的基础上稍做修改即可。

void xxs(){
	mu[1] = 1;
	for(int i = 2;i <= n;++i){
		if(!noprime[i]){
			prime[++prime[0]] = i;
			mu[i] = -1;
		}
		for(int j = 1,k;j <= prime[0] && (k = i * prime[j]) <= n;++j){
			noprime[k] = 1;
			if(i % prime[j] == 0)break;
			else mu[k] = -mu[i];
		}
	}
}

莫比乌斯反演

有了 \(\mu\) 函数的基础，我们就可以看莫比乌斯繁衍反演了。

定理

定义 \(F(n)\) 和 \(f(n)\) 是定义在非负整数集合上的两个函数，并且满足条件：

\[F(n)=\sum_{d|n}f(d) \]

那么一定存在：

\[f(n)=\sum_{d|n}\mu(d)F(\lfloor\frac{n}{d}\rfloor) \]

此定理即为莫比乌斯定理。

证明

通过定义证明：
由 \(F(n)\) 和 \(f(n)\) 的定义可得：

\[F(\left \lfloor \frac{n}{d} \right \rfloor) = \sum_{i|\left \lfloor \frac{n}{d} \right \rfloor}\ f(i) \]

那么

\[\sum_{d|n}\mu(d)F(\lfloor\frac{n}{d}\rfloor)=\sum_{d|n}\mu(d)\sum_{i|\lfloor\frac{n}{d}\rfloor}f(i) \]

\[=\sum_{i|n}f(i)\sum_{d|\lfloor\frac{n}{i}\rfloor}\mu(d)=f(n) \]

  • 另一个式子：
    当 \(F(n)\) 和 \(f(n)\) 满足：

\[F(n)=\sum_{n|d}f(d) \]

得到：

\[f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d) \]

例题1

YY的GCD

题目链接

莫比乌斯反演的开始。

首先记录一个套路：在 \(gcd\) 问题中，通常把反演中的 \(f(d)\) 设为 \(gcd(i,j)=d\)的个数， \(F(n)\) 设为 \(\sum_{base=1}^{d\times base \leqslant n} [gcd(i,j)=d\times base]\) ，即 \(gcd(i,j)=d\) 和 \(d\) 的倍数的个数。

在这个题中，我们不这样定义（因为不好证），这道题要求的是

\[\sum_{i=1}^{n}\sum_{j=1}^{m}\ gcd(i,j)\in prime \]

所以朴素算法就是，我们可以枚举每一个质数，进行求和，也就是这样：

\[\sum_{k\in prime}\sum_{i=1}^{n}\sum_{j=1}^{m}\ [gcd(i,j)=k] \]

我们直接把 \(k\) 在后两个式子中除去，得到：

\[\sum_{k\in prime}\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k}\right \rfloor}\ [gcd(i,j)=1] \]

然后开始繁衍反演。
由于只有在 \(gcd(i,j)=1\) 时才有贡献，那么我们就可以根据第一个莫比乌斯函数的性质（忘了往上翻）把最后一个 \(gcd(i,j)=1\) 进行转换，变为：

\[\sum_{k\in prime}\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k}\right \rfloor}\sum_{d|gcd(i,j)}\mu(d) \]

那么在这里， \(d\) 一定是 \(gcd(i,j)\) 的倍数，所以我们就可以继续化简，在 \(i\)，\(j\) 的极限值上同时除以一个 \(d\) ，直接乘在式子里即可，然后枚举 \(d\)。得到：

\[\sum_{k\in prime}\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\mu(d)\times \left \lfloor \frac{m}{kd} \right \rfloor\times \left \lfloor \frac{n}{kd} \right \rfloor \]

这样的时间复杂度还是不对的，因为最大的 \(n,m\) 是 \(10^7\)，所以我们就可以（不得不）继续化简。
设 \(tmp=kd\) ，那么原式子就变成了：

\[\sum_{k\in prime}\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\mu(d)\times \left \lfloor \frac{m}{tmp} \right \rfloor\times \left \lfloor \frac{n}{tmp} \right \rfloor \]

我们再对这个式子化简，把 \(tmp\) 提前枚举，那么我们就得到了最终的式子：

\[\sum_{tmp=1}^{n}\times \left \lfloor \frac{m}{tmp} \right \rfloor\times \left \lfloor \frac{n}{tmp} \right \rfloor\times (\sum_{k|tmp\ \&\&\ k \in prime}\mu(\frac{tmp}{k})) \]

最后这个式子我们可以在线性筛的时候用迪利克雷前缀和来搞一个前缀和，然后在下边只需要用整除分块的思想枚举 \(tmp\) ，每一块的和就能求出来了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+10;
int mu[maxn],noprime[maxn],prime[maxn];
int sum[maxn],f[maxn];
int n;
void xxs(){
	mu[1] = 1;
	noprime[1] = 1;
	for(int i = 2;i <= 10000000;++i){
		if(!noprime[i]){
			prime[++prime[0]] = i;
			mu[i] = -1;
		}
		for(int j = 1,k;j <= prime[0] && (k = i * prime[j]) <= 10000000;++j){
			noprime[k] = 1;
			if(i % prime[j] == 0)break;
			else mu[k] = -mu[i];
		}
	}
	for(int i = 1;i <= prime[0];++i){
		for(int j = 1;j * prime[i] <= 10000000;++j){
			f[j * prime[i]] += mu[j];
		}
	}
	for(int i = 1;i <= 10000000;++i){
		sum[i] = sum[i-1] + f[i];
	}
}
#define ll long long
int main(){
	xxs();
	int T;
	scanf("%d",&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 = 0;l <= n;l = r + 1){
			r = min(n / (n / l),m / (m / l));
			ans += (ll)(sum[r] - sum[l-1]) * (ll)(n / l) * (ll)(m / l);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

莫比乌斯反演的一些知识就到这里，其考察的一些题都是一些推柿子，所以需要慢慢钻研。筛法以后可能会更新（那得看我会不会退役），持续更新（咕咕咕）。

\(Never\ Give\ Up\)

相关文章