莫比乌斯函数&莫比乌斯反演

前置知识

带*表示如果只是学会可以不会这个知识点，但是较难的题目里面需要用到。

狄利克雷卷积

详见数论函数&狄利克雷卷积。

线性筛

详见线性筛

整除分块

详见整除分块

*杜教筛

详见杜教筛

莫比乌斯函数

莫比乌斯函数的定义

[large mu(n)=egin{cases} 1,n=1\ (-1)^k,n=prodlimits_{i=1}^k p_i^{a_i},a_i=1 (即n的所有k个质因子指数均为1的时候) \0，otherwiseend{cases} ]

莫比乌斯函数的积性

莫比乌斯函数是个积性函数，但是不是完全积性函数。

也就是说有：

[large mu(n) imes mu(m)=mu(nm) （(n,m)=1） ]

证明：

分类讨论：

先讨论两者至少一个满足第三个情况的：

因为 (0) 和任何数相乘都是 (0) ，那么显然左侧是 (0) ，对于右侧：

有一个数的素因数最高次幂 (> 1)，那么代表这个乘积的素因数最高次幂也一定 (>1) ，那么肯定会取到 (0) 。

接下来讨论 (n,m) 都不满足第三个情况的：

存在至少一个第一种情况的时候很好讨论，这里略去。

这里讨论两个都是第二种情况的时候：

因为 (n,m) 互质，所以它们没有相同的素因子，于是：

设 (large n=prodlimits_{i=1}^{k_1}p_{i_1}^{a_{i_1}},m=prodlimits_{i=1}^{k_2}p_{i_2}^{a_{i_2}})

那么 (nm) 就可以写成：

(large nm=prodlimits_{i=1}^{k_1}p_{i_1}^{a_{i_1}}prodlimits_{i=1}^{k_2}p_{i_2}^{a_{i_2}}=prodlimits_{i=1}^{k_1+k_2}p_{i_3}^{a_{i_3}})

而且这里的所有 (a_{i_3}) 都是 (1) 。

那么就变成了讨论 (k_1+k_2) 的奇偶性，这时，我们可以观察到，如果出现第一种情况，那么其实可以看做是 (k=0) 的，而 (k) 为偶数的时候又恰好 ((-1)^k=1) 。

也就是说，如果 (k_1) 和 (k_2) 奇偶性相同，那么等式左边只能是 ((-1) imes (-1)=1) 或者 (1 imes 1=1) ，这时等式右边也恰好是 (1)

如果不同，那么等式左边也只能是 ((-1) imes 1=-1) ，这时等式右边也恰好是 (-1)

(Q.E.D.)

莫比乌斯函数常见性质

(mu * I=varepsilon, mu*id=varphi, mu * d=I)

写成和式也就是：

[large egin{split} &sumlimits_{dmid n}mu(d)=[n=1] \ &sumlimits_{dmid n}mu(d)dfrac nd=varphi(n) \ &sumlimits_{dmid n}mu(d)d(dfrac nd)=1 end{split} ]

证明略。

莫比乌斯函数常见求法

线性筛

int prime[N],mu[N],cnt,pre[N],val[N];
bool isprime[N];
void GetPrimes(int v){
	mu[1]=pre[1]=1;
	for(int i=2;i<=v;i++){
		if(!isprime[i]) prime[++cnt]=i,mu[i]=-1;
		pre[i]=pre[i-1]+mu[i];
		for(int j=1;j<=cnt&&prime[j]*i<=v;j++){
			isprime[i*prime[j]]=true;
			if(i%prime[j]==0) break;
			mu[i*prime[j]]=-mu[i];
		}
	}
	return ;
}

分解质因数

直接按照定义暴力分解质因数即可。

代码：

#define ll long long
#define ull unsigned long long
#define ld long double 
inline ll mul(ll x,ll y,ll mod){
	ll res=x*y-mod*(ll)((ld)x/mod*y);
	if(res<0)return res+mod;
	if(res<mod)return res;
	return res-mod;
}
ll QuickPow(ll x,ll y){
	ll res=1;
	for(;y;y>>=1,x=x*x%MOD) if(y&1) res=res*x%MOD;
	return res;
}
ll Quick_Pow(ll x,ll y,ll mod=-1){
	ll res=1;
	for(;y;y>>=1,x=mul(x,x,mod)) if(y&1) res=mul(res,x,mod);
	return res;
}
ll test[3]={2,61};
inline bool Miller_Rabin(ll x){
	if(x==1) return false;
	ll t=x-1,k=0;
	while(!(t&1)) t>>=1,k++;
	for(int i=0;i<2;i++){
		if(x==test[i]) return true;
		ll a=Quick_Pow(test[i],t,x),Nex=a;
		for(int j=1;j<=k;j++){
			Nex=mul(a,a,x);
			if(Nex==1&&a!=1&&a!=x-1) return false;
			a=Nex;
		}
		if(a!=1) return false;
	}
	return true;
}
inline bool prime(ll x){
    if(x==46856248255981ll||x<2)return false;
    if(x==2||x==3||x==7||x==61||x==24251) return true;
    return Miller_Rabin(x);
}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
inline ll f(ll x,ll c,ll mod){
	ll res=mul(x,x,mod)+c;
	return res<mod?res:res-mod;
}
inline ll Pollard_Rho(ll x){
	ll c=rand()%(x-1),s=0;
	for(ll lim=1;;lim<<=1){
		ll t=s,now=1;
		for(ll j=1;j<=lim;j++){
			s=f(s,c,x);
			now=mul(now,abs(s-t),x);
			if(!now){ll d=gcd(s,x);if(d>1)return d;return x;}
			if(j%127==0){ll d=gcd(now,x);if(d>1)return d;}
		}
		ll d=gcd(s,x);
		if(d>1) return d;
	}
}
ll Maxn;
ll t[N],q,id,fl;
map<int,int>Map;
inline void GetFact(ll x){
	if(fl) return ;
	if(x<=1) return ;
	if(prime(x)){
		if(Map[x]) fl=true;
		Map[x]=1;id++;
		return ;
	}
	ll p=Pollard_Rho(x);
	while(p>=x) p=Pollard_Rho(x);
	GetFact(x/p),GetFact(p);
	return ;
}
inline int mu(int x){
	fl=false;id=0;map<int,int>mapp;swap(mapp,Map);
	GetFact(x);
	if(fl) return 0;
	return ((id&1)?-1:1);
}

莫比乌斯反演

对于两个定义在非负整数域上的两个函数 (f(n)) 和 (g(n))

子集形式（因数形式）

公式

如果满足：

[large g(n)=sum_{d|n} f(d) ]

那么有：

[large f(n)=sum_{d|n} mu(d) g(frac{n}{d}) ]

证明1

[large egin{split} & sum_{d|n}mu(d) g(frac{n}{d})\ &=sum_{d|n}mu(d) sum_{k|frac{n}{d}} f(k)\ &=sum_{k|n} f(k)sum_ {d|frac{n}{k}} mu(d)\ &=sum_{k|n} f(k)sum_ {d|frac{n}{k}} mu(d)\ &=f(n) end{split} ]

证明2（狄利克雷卷积）

已知 (f=g*I) ，证明 (g=f*mu)

易知如下转化：(f*mu=g*I*muRightarrow f*mu=g)

超集形式（倍数形式）

公式

如果满足：

[large g(n)=sum_{n|d} f(d) ]

那么有：

[large f(n)=sum_{n|d} mu(dfrac dn) g(d) ]

证明

[large egin{aligned} &sum_{n|d}{mu(frac{d}{n})g(d)} \ =& sum_{k=1}^{+infty}{mu(k)g(kn)} = sum_{k=1}^{+infty}{mu(k)sum_{kn|d}{f(d)}} \ =& sum_{n|d}{f(d)sum_{k|frac{d}{n}}{mu(k)}} = sum_{n|d}{f(d)varepsilon(frac{d}{n})} \ =& f(n) end{aligned} ]

莫比乌斯函数/反演基础应用

求 gcd 为某个数的数对个数

问题

求

[large sumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)=d] ]

结论

[large g(d)=sumlimits_{t=1}^{min(n,m)} mu(t) lfloordfrac n{td} floorlfloor dfrac m{td} floor ]

分析

也就是一般有这样的套路，设函数 (g(d)) 为：

[large g(d)=sumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)=d] ]

这时我们可以观察我们的函数 (f) ：

[large f(d)=sumlimits_{dmid n}g(n)=sumlimits_{dmid n}sumlimits_{i=1}^Nsumlimits_{j=1}^M[gcd(i,j)=d] ]

发现这时的 (f) 函数性质非常好，就相当于取两个数使得他们都是 (d) 的倍数，可以直接写出：

[large f(d)=lfloordfrac Nd floorlfloor dfrac Md floor ]

然后我们尝试通过莫比乌斯反演来求出 (g) 就是利用 (f) ：

[large g(n)=sumlimits_{n|d} mu(frac{d}{n}) f(d) ]

那么就是：

[large g(n)=sumlimits_{n|d} mu(frac{d}{n}) lfloordfrac Nd floorlfloor dfrac Md floor ]

然后我们换成直接枚举这个倍数 (large t=frac dn) ：

[large g(n)=sumlimits_{t=1}^{{min(N,M)}}mu(t) lfloordfrac N{tn} floorlfloor dfrac M{tn} floor ]

那么对于这个柿子可以应用整除分块来处理后半部分，然后预处理一下 (mu) 的前缀和即可在 (sqrt{N}) 的复杂度做到 (O(n)) 预处理的单次询问

注意这里的整除分块：

其实我们不是按照 (tn) 来分块（这样我就不会处理 (mu) 里面的东西了），而是 (t) 来分块。

要把柿子转化成这样：

[large g(n)=sumlimits_{t=1}^{min(N,M)} mu(t) lfloordfrac{lfloorfrac N{t} floor}{n} floorlfloordfrac{lfloorfrac M{t} floor}{n} floor ]
然后这个时候以 (t) 来分块看上去就很没有问题了，因为变量只有 (t) ，和 (n) 没有关系，我们只关注分子的变化即可。

接下来可以注意这样的分块，其实就等价于 (N,M) 都来分块，分了很多个隔板，然后块的个数也就是 (2sqrt{N}) 级别了。

也就是每次取 (r) 的时候取两者算出来较小的右端点。