莫比乌斯反演笔记

对于一些函数,如果它本身的值难以求得,但对应约数容易求,那么可以考虑反演来简化运算.
本帖收录一些本人写过的反演题,
资料参考:
OIWIKI
求解莫比乌斯函数的模板（利用线性筛）

int mu[maxn];int pr[maxn];ll sum[maxn];bool vis[maxn];
void getMu(int n){
	mu[1] = 1;int tot = 0;
	for(int i=2;i<=n;i++){
		if(!vis[i]) pr[++tot] = i,mu[i]=-1;
		for(int j=1;j<=tot&&i*pr[j]<=n;j++){
			vis[i*pr[j]] = 1;
			if(i%pr[j]==0) {
				mu[i*pr[j]]=0;break;
			}
			mu[i*pr[j]] = -mu[i];
 		}
	}
	for(int i=1;i<=n;i++) sum[i] = sum[i-1]+mu[i];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

主要有两种反演形式:


然后关于gcd(i,j)==1这个东西,实际上有以下套路.


那样gcd(i,j)就会拆成一个和式,对于这个和式还能进一步拆分,利用积分变换顺序的原则(求和看作积分的一种情况)
先看例题,直接运用了上述结论.
P3455 [POI2007]ZAP-Queries


主要是多次变换求和的顺序,让无关的元素提出去。
最后,我们发现该式子只与莫比乌斯函数的前缀和,和一个取整的东西有关.
此时,已经可以做到O(n)回答该问题了,但仍然不能完成题目需求.
这时候,有个东西叫数论分块.就是由于取整函数的性质,其实有一堆在线性枚举d的时候$n/(k\ast d)\ast m/(k\ast d)$值是一样的,我们考虑把这些块打包计算,这种思想就叫数论分块.
先求出莫比乌斯函数前缀和,再运用数论分块计算贡献即可.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
int mu[maxn];int pr[maxn];ll sum[maxn];bool vis[maxn];
void getMu(int n){
	mu[1] = 1;int tot = 0;
	for(int i=2;i<=n;i++){
		if(!vis[i]) pr[++tot] = i,mu[i]=-1;
		for(int j=1;j<=tot&&i*pr[j]<=n;j++){
			vis[i*pr[j]] = 1;
			if(i%pr[j]==0) {
				mu[i*pr[j]]=0;break;
			}
			mu[i*pr[j]] = -mu[i];
 		}
	}
	for(int i=1;i<=n;i++) sum[i] = sum[i-1]+mu[i];
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	getMu(50000);
	while(T--){
		ll n,m,k;cin>>n>>m>>k;
		ll ans = 0;
		for(ll l=1,r=0;l<=min(n,m);l=r+1){
			r = min(n/(n/l),m/(m/l));
			ans+=(sum[r]-sum[l-1]) * (n/(l*k)) * (m/(l*k));
		}
		cout<<ans<<"\n";
	}
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

P2257 YY的GCD

差不多的套路,但是需要一些数学上的灵感.
借助上题的经验,可以知道类似地推导过程,得到下列笔记最后的一个式子.

此时已经陷入僵局了。直接做肯定T的飞起,不仅要枚举素数集合,还要枚举内层的两个取整函数贡献.
回想上一题的做法,利用数论分块,我们把取整值相同的情况进行了打包计算,这迫使我们想把取整函数提取出来。
从高等数学中,一般通过变化未知量,采取换元的方法来做到这点.
不妨令$T=k\ast d$,再变换求和符号中的$d$与$T$,这样我们可以把取整函数取出来放到第一个求和中.
具体做法如下图,

得到了这些东西,足以求解本题,以下为代码:

#include
using namespace std;
const int maxn = 1e7+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
int mu[maxn];int pr[maxn];ll sum[maxn];bool vis[maxn];
ll res[maxn];
void getMu(int n){
	mu[1] = 1;int tot = 0;
	for(int i=2;i<=n;i++){
		if(!vis[i]) pr[++tot] = i,mu[i]=-1;
		for(int j=1;j<=tot&&i*pr[j]<=n;j++){
			vis[i*pr[j]] = 1;
			if(i%pr[j]==0) {
				mu[i*pr[j]]=0;break;
			}
			mu[i*pr[j]] = -mu[i];
 		}
	}
	for(int i=1;i<=tot;i++){
		for(int j=1;j*pr[i]<=n;j++){
			res[j*pr[i]]+=mu[j];
		}
	}
	for(int i=1;i<=n;i++) sum[i] = sum[i-1] + res[i];
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int MAX = 1e7;
	getMu(MAX);
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		ll ans = 0;
		for(int l=1,r;l<=min(n,m);l = r+1){
			r = min(n/(n/l),m/(m/l));
			ans+= (sum[r]-sum[l-1]) *(n/l)*(m/l);
		}
		cout<<ans<<"\n";
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

P2522 [HAOI2011]Problem b

似乎是例题1的容斥版本.考虑到下界不是1开始的,考虑用容斥把多余的部分扣除掉.
那么每一部分都是例题1的情况.二维容斥下就好

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
int mu[maxn];int pr[maxn];int sum[maxn];bool vis[maxn];
void getMu(int n){
	mu[1] = 1;int tot = 0;
	for(int i=2;i<=n;i++){
		if(!vis[i]) pr[++tot] = i,mu[i]=-1;
		for(int j=1;j<=tot&&i*pr[j]<=n;j++){
			vis[i*pr[j]] = 1;
			if(i%pr[j]==0) {
				mu[i*pr[j]]=0;break;
			}
			mu[i*pr[j]] = -mu[i];
 		}
	}
	for(int i=1;i<=n;i++) sum[i] = sum[i-1]+mu[i];
}
int k;
int get(int n,int m){
	int ans = 0;
	for(int l=1,r=0;l<=min(n,m);l=r+1){
		r = min(n/(n/l),m/(m/l));
		ans+=(sum[r]-sum[l-1]) * (n/(l*k)) * (m/(l*k));
	}
	return ans;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	int MX = 5e4+5;
	getMu(MX);
	while(T--){
		int a,b,c,d;
		cin>>a>>b>>c>>d>>k;
		int ans = get(b,d) - get(a-1,d) - get(b,c-1) + get(a-1,c-1);
		cout<<ans<<"\n";
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48