莫比乌斯反演学习笔记

在Imagine大佬的博客帮助下整了一周莫某某反演,总结一下学的一些新东西和我做的水题的一些小套路;

本篇文章没有对反演进行证明,只是记录了一些理解与做题时遇到的感觉挺有用的小技巧

首先是莫比乌斯函数(mu)

[mu(x)=egin{cases} x=1 　　　　　　　　　　1\ x=p_1^1*p_2^1*p_3^1...*p_k^1　　　(-1)^k\ Other　　　　　　　　　　0\ end{cases}]

有(sum_{d|n}mu(d)=[n=1])
是积性函数
可以用线性筛在(O(n))的时间内得到

void Prepare() {
	mu[1]=1;
	for(int i=2;i<=MAX;++i) {
		if(!sign[i]) pri[++cnt]=i,mu[i]=i-1;
		for(int j=1;i*pri[j]<=MAX;++j) {
			sign[i*pri[j]]=true;
			if(i%pri[j]==0) {
				mu[i*pri[j]]=0;
				break;
			}
			else mu[i*pri[j]]=-mu[i];
		}
	}
}

丢一道题BZOJ2440,容斥的时候也可以考虑一下莫比乌斯函数;

然后是狄利克雷卷积

有两个数列函数(f),(g),它们的狄利克雷卷积定义为((f*g)(n)=sum_{d|n}f(d)*g(frac{n}{d}));
若(f)和(g)都是积性函数,则它们的狄利克雷卷积也为积性函数;
狄利克雷卷积满足交换律、结合律，对加法满足分配律

最后是莫比乌斯反演

先说反演,反演在干个什么事呢,我的理解就是给了你一些已知量,然后未知量和已知量直接有某种运算关系,然后通过已知量反解出未知量的过程就是反演;
而莫比乌斯反演也是干这样的事,若函数(f),(g)满足这样的关系:

[f(n)=sum_{d|n}g(d)$$那么有:$$g(n)=sum_{d|n}mu(frac{n}{d})*f(d)$$这个式子证明的话比较简单,考虑狄利克雷卷积$f=g*I$($I$为恒等函数$I(n)=1$,完全积性),然后同时在两边卷上一个$mu$,$f*mu=g*I*mu=g*e=g$($e$为狄利克雷卷积的乘法单位元函数$e(n)=[n=1]$,完全积性); 这个式子还有另一种形式: 若$$f(n)=sum_{n|d}g(d)$$那么$$g(n)=sum_{n|d}mu(frac{d}{n})*f(d)]

这个的具体证明也是大力展开式子,具体可看其他人博客(逃

有了这两个关系式之后我们能干些啥事呢?
就像刚刚所说,我们可以通过很快算出其中一个函数的取值,再通过莫比乌斯反演反解出另一个函数,从而大大降低复杂度;

(接下来如果式子中同时出现了(n)和(m),默认(nleq m));

来看道例题BZOJ1101
这道题需要求的就是(sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d])
设函数(g(d)=sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d]),我们发现主要的困难点就是这个(g(d))感觉起码要花(O(n^2))的代价去算这个东西,有多组询问这样复杂度就变成了(O(n^3))以上了,怎么办呢,想起莫比乌斯反演,如果我们能找一个满足反演式子,切算起来复杂度很低的式子,我们是不是就能够很快解决这个问题呢?这题的这个式子很好找而且很套路,设(f(k)=sum_{i=1}^nsum_{j=1}^m[k|gcd(i,j)]),(f(k))就相当于找(gcd(i,j))是(k)的倍数的(i,j)对数,这样是可以(f)直接算出来的,有(f(k)=left lfloorfrac{n}{k} ight floorleftlfloorfrac{m}{k} ight floor),那么进行反演
有$$f(k)=sum_{k|d}g(d)$$
则$$g(d)=sum_{d|k}mu(frac{k}{d})f(k)$$$$g(d)=sum_{i=1}{leftlfloorfrac{n}{d} ight floor}mu(i)f(id)$$$$g(d)=sum_{i=1}{leftlfloorfrac{n}{d} ight floor}mu(i)left lfloorfrac{n}{id} ight floorleftlfloorfrac{m}{id} ight floor$$现在我们只需要O(n)的时间,便能完成一次询问了,但是还不够,因为这道题是多组询问,这个时候就要用的一个非常常用的小技巧数论分块了;
当式子里出现这么个东西(sum_{i=1}^nleft lfloorfrac{n}{i} ight floor),考虑(left lfloorfrac{n}{i} ight floor)的取值,很容易看出当(1leq ileq sqrt n)的时候(left lfloorfrac{n}{i} ight floor)最多有(sqrt n)个取值,当(sqrt nleq ileq n)的时候,(left lfloorfrac{n}{i} ight floor)也最多只有(sqrt n)个取值,且这些区间是连续的,那么我们就可以一次性把所有取值相同的(i)一起算完,比如(i=d)的时候是一个新取值区间的左端点,右端点便是(left lfloorfrac{n}{left lfloorfrac{n}{i} ight floor} ight floor),那么在(O(sqrt n))的时间内我们就能得到(sum_{i=1}^nleft lfloorfrac{n}{i} ight floor)的答案;
(left lfloorfrac{n}{id} ight floorleftlfloorfrac{m}{id} ight floor)同理,只是注意在取右端点的时候要取更靠左的那一个,详细看代码;

#include<bits/stdc++.h>
#define Fst first
#define Snd second
#define RG register
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
template<typename T> inline void read(T& x) {
	char c = getchar();
	bool f = false;
	for (x = 0; !isdigit(c); c = getchar()) {
		if (c == '-') {
			f = true;
		}
	}
	for (; isdigit(c); c = getchar()) {
		x = x * 10 + c - '0';
	}
	if (f) {
		x = -x;
	}
}
template<typename T, typename... U> inline void read(T& x, U& ... y) {
	read(x), read(y...);
}
const int MAX=5e4,N=MAX+10;
int cnt,Q;
int pri[N],mu[N];
bool sign[N];
void Prepare() {
	mu[1]=1;
	for(int i=2;i<=MAX;++i) {
		if(!sign[i]) pri[++cnt]=i,mu[i]=-1;
		for(int j=1;i*pri[j]<=MAX;++j) {
			sign[i*pri[j]]=true;
			if(i%pri[j]==0) {
				mu[i*pri[j]]=0;
				break;
			}
			else mu[i*pri[j]]=-mu[i];
		}
	}
	for(int i=1;i<=MAX;++i) mu[i]+=mu[i-1];
}
LL Calc(int n,int m,int d) {
	if(n>m) swap(n,m);
	n/=d; m/=d;
	LL res=0;
	for(int i=1;i<=n;++i) {
		int p=min(n/(n/i),m/(m/i));
		res+=1ll*(mu[p]-mu[i-1])*(n/i)*(m/i);
		i=p;
	}
	return res;
}
int main() {
#ifdef rua
	freopen("GG.out","w",stdout);
#endif
	Prepare();
	read(Q);
	while(Q--) {
		int n,m,d; read(n,m,d);
		printf("%lld
",Calc(n,m,d));
	}
	return 0;
}

接下来的题每道都会带一些小技巧,比如式子的替换或者一些函数怎么拆开;

接下来的除法,除非做特殊说明否则都是向下取整(向下取整符号真的难打

BZOJ2154
这题是叫你求(sum_{i=1}^nsum_{j=1}^mlcm(i,j))
看到(lcm)往往要拆成(gcd),所以式子化为$$sum_{i=1}nsum_{j=1}mfrac{ij}{gcd(i,j)}$$
然后提(gcd)出来

[sum_{d=1}^nsum_{i=1}^nsum_{j=1}^mfrac{ij}{d}[gcd(i,j)=d] ]

再把(d)提出来方便分析

[sum_{d=1}^nsum_{i=1}^{frac{n}{d}}sum_{j=1}^{frac{m}{d}}frac{idjd}{d}[gcd(i,j)=1] ]

[sum_{d=1}^ndsum_{i=1}^{frac{n}{d}}sum_{j=1}^{frac{m}{d}}ij[gcd(i,j)=1] ]

有这个(ij)在后面卡着我们不好反演,这时想起一个好东西(sum_{d|n}=[n=1]),我们正好把后面的(gcd)换了;

[sum_{d=1}^ndsum_{i=1}^{frac{n}{d}}sum_{j=1}^{frac{m}{d}}ijsum_{x|i,x|j}mu(x)$$; 遇到枚举因子的就尝试把因子提到前面来; $$sum_{d=1}^ndsum_{x=1}^{frac{n}{d}}mu(x)sum_{i=1}^{frac{n}{dx}}sum_{j=1}^{frac{m}{dx}}ixjx$$; $$sum_{d=1}^ndsum_{x=1}^{frac{n}{d}}mu(x)x^2sum_{i=1}^{frac{n}{dx}}sum_{j=1}^{frac{m}{dx}}ij$$; 设$Sum(a,b)=sum_{i=1}^asum_{j=1}^bij$,这个东西其实也是可以直接算的,它显然等于$frac{a*(a+1)}{2}*frac{b*(b+1)}{2}$,那么 $$sum_{d=1}^ndsum_{x=1}^{frac{n}{d}}mu(x)x^2Sum(frac{n}{dx},frac{m}{dx})$$; 那么我们可以在算$Sum$的时候分块一次,算整体的$sum_{x=1}^{frac{n}{d}}mu(x)x^2Sum(frac{n}{dx},frac{m}{dx})$时候又分块一次,这样我们便能在$O(n)$的时间内解决这道题了; 接着看这道题的加强版[BZOJ2693](https://www.lydsy.com/JudgeOnline/problem.php?id=2693) 在上一题的基础上,这题变成了多组询问,$O(n)$的复杂度似乎还是不够优秀,我们继续推式子$$sum_{d=1}^ndsum_{x=1}^{frac{n}{d}}mu(x)x^2Sum(frac{n}{dx},frac{m}{dx})]

这也是个常用技巧,设(T=dx),我们变换下标,把它提到前面去看看怎么样$$sum_{T=1}nSum(frac{n}{T},frac{m}{T})sum_{d|T}d*mu(frac{T}{d})*(frac{T}{d})2$$
现在我们来观察一下后面这坨东西

[sum_{d|T}d*mu(frac{T}{d})*(frac{T}{d})^2 ]

(d)和((frac{T}{d})^2)都可以看作幂函数(id^k(n)=n^k),完全积性,(mu)函数,积性函数;

(　　　　　　　　　) 在这里插入图片描述

这坨东西好像可以筛;

设$$g(n)=sum_{d|n}dmu(frac{n}{d})(frac{n}{d})^2$$
现在考虑(n=1)时(g(n)=1)
当(n)为质数时,(d)只有(1)和(n)两种取值,此时(g(n)=n-n^2)
当(n)不为质数时,考虑唯一分解定理(g(n)=prod_{p_i为n的质因子}^tg(p_i^{c_i}))
考虑线性筛的两种情况,第一种(i\%pri[j]!=0)时,因为(g)是积性函数,(g(i*pri[j])=g(i)*g(pri[j]))
否则考虑新进来一个质数(p)会增加怎样的新因子,因为如果(mu(d))的(d)中含有二次以上的因子,必然会等于(0),此时发现原来那些有效的因子(d),乘上一个(p)后继续有效,其他的(d)都因为(frac{n}{d})含有了二次以上的因子导致(mu(d)=0)可以不用考虑了,所以此时的(g(i*pri[j])=g(i)*pri[j]);
所以我们可以用线性筛先预处理出所有的(g(T)),现在式子变成$$sum_{T=1}^nSum(frac{n}{T},frac{m}{T})g(T)$$
再加上除法分块,我们便能在(O(sqrt n))的时间内完成一次询问了;

#include<bits/stdc++.h>
#define Fst first
#define Snd second
#define RG register
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
template<typename T> inline void read(T& x) {
	char c = getchar();
	bool f = false;
	for (x = 0; !isdigit(c); c = getchar()) {
		if (c == '-') {
			f = true;
		}
	}
	for (; isdigit(c); c = getchar()) {
		x = x * 10 + c - '0';
	}
	if (f) {
		x = -x;
	}
}
template<typename T, typename... U> inline void read(T& x, U& ... y) {
	read(x), read(y...);
}
const int MAX=1e7,N=MAX+10,P=20101009;
int cnt,T;
int F[N],G[N],pri[N];
bool sign[N];
void Prepare() {
	F[1]=1;
	for(int i=2;i<=MAX;++i) {
		if(!sign[i]) pri[++cnt]=i,F[i]=(i-1ll*i*i%P+P)%P;
		for(int j=1;i*pri[j]<=MAX;++j) {
			sign[i*pri[j]]=true;
			if(i%pri[j]==0) {
				F[i*pri[j]]=1ll*F[i]*pri[j]%P;
				break;
			}
			else F[i*pri[j]]=1ll*F[i]*F[pri[j]]%P;
		}
	}
	for(int i=1;i<=MAX;++i) F[i]=(F[i]+F[i-1])%P,G[i]=(1ll*i*(i+1)/2ll)%P;
}
int Calc(int n,int m) {
	if(n>m) swap(n,m);
	int res=0;
	for(int i=1;i<=n;++i) {
		int p=min(n/(n/i),m/(m/i));
		res=(res+1ll*((F[p]-F[i-1])%P+P)%P*G[n/i]%P*G[m/i]%P)%P;
		i=p;
	}
	return res;
}
int main() {
#ifdef rua
	freopen("GG.out","w",stdout);
#endif
	Prepare();
	T=1;
	while(T--) {
		int n,m; read(n,m);
		printf("%d
",Calc(n,m));
	}
	return 0;
}

BZOJ2005
这题抽象一下之后,我们的重点就是求(sum_{i=1}^nsum_{j=1}^mgcd(i,j))
本题可以用上面那个(O(sqrt n))的反演求(gcd=d)的个数暴力去跑(n)次得到答案;
但是这里要介绍另外一种方法,因为这个方法经常用于式子的替换上;
这里不再是,求个数了,而是具体的和,于是可以用的欧拉函数(varphi)的一个性质$$n=sum_{d|n}varphi(d)$$
于是式子变成了这样$$sum_{i=1}nsum_{j=1}msum_{d|i,d|j}varphi(d)$$
很套路的把(d)提到前面来$$sum_{d=1}^nvarphi(d)frac{n}{d}frac{m}{d}$$
数论分块一下,跑的比反演不知道快到哪里去了了;

#include<bits/stdc++.h>
#define Fst first
#define Snd second
#define RG register
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
template<typename T> inline void read(T& x) {
    char c = getchar();
    bool f = false;
    for (x = 0; !isdigit(c); c = getchar()) {
        if (c == '-') {
            f = true;
        }
    }
    for (; isdigit(c); c = getchar()) {
        x = x * 10 + c - '0';
    }
    if (f) {
        x = -x;
    }
}
template<typename T, typename... U> inline void read(T& x, U& ... y) {
    read(x), read(y...);
}
const int MAX=1e5,N=MAX+10;
int cnt;
int pri[N];
bool sign[N];
LL phi[N];
void Prepare() {
    phi[1]=1;
    for(int i=2;i<=MAX;++i) {
        if(!sign[i]) pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;i*pri[j]<=MAX;++j) {
            sign[i*pri[j]]=true;
            if(i%pri[j]==0) {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
    for(int i=1;i<=MAX;++i) phi[i]+=phi[i-1];
}
int main() {
#ifdef rua
    freopen("GG.in","r",stdin);
#endif
    Prepare();
    int n,m; read(n,m);
    if(n>m) swap(n,m);
    LL res=-1ll*n*m;
    for(int i=1;i<=n;++i) {
    	int p=min(n/(n/i),m/(m/i));
    	res+=(phi[p]-phi[i-1])*(n/i)*(m/i)*2;
    	i=p;
    }
    printf("%lld
",res);
    return 0;
}

换(varphi)的时候往往会把一些比较复杂的反演变成非常简单的筛(varphi)

推荐一些题,因为做的难度中等偏下,可能会比较水;
BZOJ2694&BZOJ4659:两道题一样的,式子推出来复杂度不够优秀不能支持多组询问,需要用的上面所说的变换下标;
BZOJ4407:同样是变换下标线性筛;
BZOJ3529:离线+树状数组;
BZOJ4816:累乘的反演,其实累乘就是在质数上相加;
LuoguP3768:本来挺复杂度反演,通过换(varphi)变成了比较水的裸杜教筛;
暂时先写那么多;

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ak12/p/10221047.html