莫比乌斯反演学习笔记

03/08 13:02
阅读数 19

莫比乌斯反演学习笔记

参考资料

https://oi-wiki.org/math/mobius/

前置知识:

整除分块 </> 积性函数 <a href="#jxhs"><讲></a> 狄利克雷卷积 <a href="#dlkl"><讲></a>


主要内容:

莫比乌斯函数 <a href="#hs"><讲></a> 莫比乌斯反演 <a href="#fy"><讲></a> 莫比乌斯例题 <a href="#lt"><讲></a>

<a href="#pro">[HAOI2011]Problem b</a> <a href="#lcm">LCMSUM</a> <a href="#cra">[国家集训队]Crash的数字表格</a> <a href="#ysg">[SDOI2015]约数个数和</a>


<a id="jxhs">积性函数</a>

定义:如果 $\gcd(x,y)=1$ 并且 $f(xy)=f(x)f(y)$,则 $f(n)$ 为积性函数。

性质:如果 $f(x)$ 和 $g(x)$ 均为积性函数,那么如下函数也是积性函数:

$$h(x)=f(x^p)$$

$$h(x)=f^p(x)$$

$$h(x)=f(x)g(x)$$

$$h(x)=\sum\limits_{d\mid x}f(d)g(\frac xd)$$

例子:

单位函数:$\epsilon(x)=[x=1]$。

常数函数:$1(x)=1$。

欧拉函数:$\varphi(x)=\sum\limits_{i=1}^x[\gcd(x,i)=1]$。

莫比乌斯函数也是,下文会讲。


<a id="dlkl">狄利克雷(Dirichlet)卷积</a>

定义:

两个数论函数 $f$ 和 $g$ 的狄利克雷卷积 $(f*g)$ 为

$$(f*g)(x)=\sum\limits_{d|x}f(d)g(\frac xd)$$

性质:满足交换和结合律,$\epsilon$ 是该函数单位元,每个函数卷它都得本身。

例子:

$$d(x)=(1*1)(x)=\sum\limits_{d|x}1$$

$$\sigma(x)=(1*d)(x)=\sum\limits_{d|x}d$$

$$\epsilon(x)=(\mu*1)(x)=\sum\limits_{d|x}\mu(d)$$

$$\varphi(x)=(\mu*ID)(x)=\sum\limits_{d|x}d\cdot\mu(\frac xd)$$

(这里的 $\mu$ 就是过会儿的莫比乌斯函数)。


<a id="hs">莫比乌斯函数</a>

定义:莫比乌斯函数符号为 $\mu$,

$$ \mu(x)= \begin{cases} 1 & x=1\ 0 & \exists d\in\mathbb{Z}:d^2\mid x\ (-1)^k & k 为 x 本质不同的的质因子个数\ \end{cases} $$

说明:如果有 $x=\prod\limits_{i=1}^kp_i^{c_i}$,那么

  1. 如果 $x=1$,那么 $\mu(x)=1$。
  2. 如果 $\forall i:c_i=1$,那么 $\mu(x)=(-1)^k$。
  3. 否则 $\mu(x)=0$。

性质:

  1. $\mu*1=\epsilon$,即 $\sum\limits_{d\mid x}\mu(d)=\epsilon(x)$,或 $$ \sum\limits_{d\mid x}\mu(d)= \begin{cases} 1 & x=1\ 0 & x\neq 1\ \end{cases} $$

  2. $\sum\limits_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}$。

  3. 反演结论:$[\gcd(i,j)=1]=\epsilon(\gcd(i,j))=\sum\limits_{d|\gcd(i,j)}\mu(d)$。

  4. 拓展:$\varphi*1=ID$,$\sum\limits_{d|nm}=\sum\limits_{x|n}\sum\limits_{y|m}[\gcd(x,y)=1]$。

线性筛求莫比乌斯函数:

void Mobius(int n){
	mu[1]=1;
	for(int i=2;i<=n;i++){
		if(!np[i]) p[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*p[j]<=n;j++){
			np[i*p[j]]=1;
			if(i%p[j]==0){mu[i*p[j]]=0;break;}
			mu[i*p[j]]=-mu[i];
		}
	}
}

<a id="fy">莫比乌斯反演</a>

如果有两个数量函数 $f$ 和 $g$,满足

$$f(x)=\sum\limits_{d|x}g(d)$$

那么就有

$$g(x)=\sum\limits_{d|x}f(d)\cdot\mu(\frac xd)$$

证明:

即已知 $f=g1$,证明 $g=f\mu$。

证:$f*\mu=g1\mu=g*\epsilon=g$。


<a id="lt">经典例题</a>

<a id="pro">[HAOI2011]Problem b</a>

[HAOI2011]Problem b

$T$ 组测试数据,给定 $a,b,c,d,k$ 求 $$\sum\limits_{i=a}^b\sum\limits_{j=c}^d[\gcd(i,j)=k]$$

数据范围:$1\le T,a,b,c,d,k\le 5\times 10^4$。


如果令

$$f(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k]$$

容斥一下,则有题目中的式子

$$=f(b,d)+f(a-1,c-1)-f(a-1,d)-f(b,c-1)$$。

然后

$$ \begin{split} f(n,m)=&\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k]\ =&\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{j=1}^{\lfloor \frac mk \rfloor}[\gcd(i,j)=1]\ =&\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{j=1}^{\lfloor \frac mk \rfloor}\epsilon(\gcd(i,j))\ =&\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{j=1}^{\lfloor \frac mk \rfloor}\sum\limits_{d\mid \gcd(i,j)}\mu(d)\ =&\sum\limits_{d=1}^{\min{n,m}}\mu(d)\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}[d\mid i]\sum\limits_{j=1}^{\lfloor \frac mk \rfloor}[d\mid j]\ =&\sum\limits_{d=1}^{\min{n,m}}\mu(d)\sum\limits_{i=1}^{\lfloor \frac n{kd}\rfloor}\sum\limits_{j=1}^{\lfloor \frac m{kd} \rfloor}\ =&\sum\limits_{d=1}^{\min{n,m}}\mu(d)\lfloor \frac n{kd}\rfloor\lfloor \frac m{kd} \rfloor\ \end{split} $$

然后用莫比乌斯函数前缀和 $+$ 整除分块计算即可,时间复杂度 $\Theta(N+T\sqrt n)$。

<details> <summary>Code</summary> ```cpp #include <bits/stdc++.h> using namespace std;

//&Start #define lng long long #define lit long double #define kk(i,n) "\n "[i<n] const int inf=0x3f3f3f3f; const lng Inf=1e17;

//&Mobius const int N=5e4; bitset<N+10> np; int mu[N+10],cnt,p[N+10]; void Mobius(){ mu[1]=1; for(int i=2;i<=N;i++){ if(!np[i]) p[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt&&ip[j]<=N;j++){ np[ip[j]]=1; if(i%p[j]==0){mu[ip[j]]=0;break;} mu[ip[j]]=-mu[i]; } } for(int i=1;i<=N;i++) mu[i]+=mu[i-1]; }

//&Fenk int Fenk(int n,int m){ int res=0,mn=min(n,m); for(int l=1,r;l<=mn;l=r+1){ r=min(n/(n/l),m/(m/l)); res+=(mu[r]-mu[l-1])(n/l)(m/l); } return res; }

//&Data int t,a,b,c,d,k;

//&Main int main(){ Mobius(); scanf("%d",&t); for(int ti=1;ti<=t;ti++){ scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); printf("%d\n", +Fenk(b/k,d/k) +Fenk((a-1)/k,(c-1)/k) -Fenk((a-1)/k,d/k) -Fenk(b/k,(c-1)/k) ); } return 0; }

</details>

---

### <a id="lcm">LCMSUM</a>

> [LCMSUM](https://www.luogu.com.cn/problem/SP5971)

> $T$ 组数据,给定 $n$,求 $$\sum\limits_{i=1}^n\operatorname{lcm}(i,n)$$

> 数据范围:$1\le T\le 3\times 10^5$,$1\le n\le 10^6$。

---

$$
\begin{split}
g(n)=&\sum\limits_{i=1}^n\operatorname{lcm}(i,n)\\
=&\sum\limits_{i=1}^n\frac{in}{\gcd(i,n)}\\
=&\sum\limits_{d|n}\sum\limits_{i=1}^n[\gcd(i,n)=d]\frac id n\\
=&\sum\limits_{d|n}\sum\limits_{i=1}^{\frac nd}[\gcd(i,\frac nd)=1]in\\
=&n\sum\limits_{d|n}\sum\limits_{i=1}^{\frac nd}[\gcd(i,\frac nd)=1]i\\
\end{split}
$$

令

$$f(n)=\sum\limits_{i=1}^n[\gcd(n,i)=1]i$$

$$\because \gcd(n,i)=\gcd(n,n-i)$$

$$\therefore [\gcd(n,i)=1]=[\gcd(n,n-i)=1]$$

$$[\gcd(n,i)=1]i+[\gcd(n,n-i)](n-i)=n[\gcd(n,i)=1]$$

$$\therefore f(n)=\sum\limits_{i=1}^n[\gcd(n,i)=1]i=\frac {\varphi(n)n}{2}$$

$$
\begin{split}
\therefore g(n)=&n\sum\limits_{d|n}f(\frac nd)\\
=&n\sum\limits_{d|n}\frac {\varphi(\frac nd)\frac nd}{2}\\
=&n\sum\limits_{d|n}\frac {\varphi(d)d}{2}\\
\end{split}
$$

然后码的时候,维护一个前缀和

$$sum(n)=\sum\limits_{d|n}\frac {\varphi(d)d}{2}$$

即可,然后总时间复杂度就是 $\Theta(n\log\log n+T)$。

 <details>
<summary>Code</summary>

```cpp
#include <bits/stdc++.h>
using namespace std;

//&Start
#define lng long long
#define lit long double
#define kk(i,n) "\n "[i<n]
const int inf=0x3f3f3f3f;
const lng Inf=1e17;

//&Eular
const int N=1e6;
bitset<N+10> np;
int phi[N+10],cnt,p[N+10];
lng f[N+10];
void Eular(){
	for(int i=2;i<=N;i++){
		if(!np[i]) p[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*p[j]<=N;j++){
			np[i*p[j]]=1;
			if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
			else phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
	f[1]=1;
	for(int i=2;i<=N;i++) f[i]=1ll*phi[i]*i/2;
	for(int j=1;j<=cnt;j++)
		for(int i=1;i*p[j]<=N;i++)
			f[i*p[j]]+=f[i]; //用f数组自得sum
}

//&Data
int t,n;

//&Main
int main(){
	Eular();
	scanf("%d",&t);
	for(int ti=1;ti<=t;ti++){
		scanf("%d",&n);
		printf("%lld\n",f[n]*n);
	}
	return 0;
}

</details>


<a id="cra">[国家集训队]Crash的数字表格</a>

[国家集训队]Crash的数字表格 / JZPTAB

单组测试数据,给定 $n,m$ ,求 $$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)\bmod 20101009$$

数据范围:$1\le n,m\le 10^7$。


$n\le m$,一气呵成:

$$ \begin{split} g(n,m)=&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{\gcd(i,j)}\ =&\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{d}[\gcd(i,j)=d]\ =&\sum\limits_{d=1}^n\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}ijd[\gcd(i,j)=1]\ =&\sum\limits_{d=1}^n d\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}i\sum\limits_{j=1}^{\lfloor\frac md\rfloor}j\sum\limits_{k|\gcd(i,j)}\mu(k)\ =&\sum\limits_{d=1}^n d\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}i[k|i]\sum\limits_{j=1}^{\lfloor\frac md\rfloor}j[k|j]\ =&\sum\limits_{d=1}^n d\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor\frac {n}{dk}\rfloor}ik\sum\limits_{j=1}^{\lfloor\frac {m}{dk}\rfloor}jk\ =&\sum\limits_{d=1}^n d\sum\limits_{k=1}^nk^2\mu(k)\frac{\lfloor\frac{n}{dk}\rfloor(\lfloor\frac{n}{dk}\rfloor+1)}{2}\cdot\frac{\lfloor\frac{m}{dk}\rfloor(\lfloor\frac{m}{dk}\rfloor+1)}{2}\ \end{split} $$

将 $x=dk$ 带入:

$$g(n,m)=\sum\limits_{x=1}^nx\cdot\frac{\lfloor\frac{n}{x}\rfloor(\lfloor\frac{n}{x}\rfloor+1)}{2}\cdot\frac{\lfloor\frac{m}{x}\rfloor(\lfloor\frac{m}{x}\rfloor+1)}{2}\sum\limits_{k|x}k\mu(k)$$

然后筛 $\mu(k)$ 时顺便计算 $h(k)=k\mu(k)$,最后狄利克雷前缀和求 $f(k)=\sum\limits_{k|x}k\mu(k)$。

别忘了膜拜 $20101009$,时间复杂度 $\Theta(N+n)$。

<details> <summary>Code</summary> ```cpp #include <bits/stdc++.h> using namespace std;

//&Start #define lng long long #define lit long double #define kk(i,n) "\n "[i<n] const int inf=0x3f3f3f3f; const lng Inf=1e17;

//&Mobius const int N=1e7; const int mod=20101009; bitset<N+10> np; int mu[N+10],cnt,p[N+10],f[N+10]; void Mobius(){ f[1]=mu[1]=1; for(int i=2;i<=N;i++){ if(!np[i]) p[++cnt]=i,mu[i]=-1; f[i]=(mu[i]i+mod)%mod; for(int j=1;j<=cnt&&ip[j]<=N;j++){ np[ip[j]]=1; if(i%p[j]==0){mu[ip[j]]=0;break;} mu[ip[j]]=-mu[i]; } } for(int j=1;j<=cnt;j++) for(int i=1;ip[j]<=N;i++) (f[i*p[j]]+=f[i])%=mod; //狄利克雷前缀和 }

//&Data int n,m,ans; int bitfun(int x){ lng res=1llxf[x]%mod; (res*=1ll*(n/x+1)(n/x)/2%mod)%=mod; (res=1ll*(m/x+1)*(m/x)/2%mod)%=mod; //如上 //这个1ll不乘要爆long long,30分。 return (int)res; }

//&Main int main(){ Mobius(); scanf("%d%d",&n,&m); if(n>m) swap(n,m); for(int i=1;i<=n;i++) (ans+=bitfun(i))%=mod; printf("%d\n",ans); return 0; }

</details>

---

### <a id="ysg">[SDOI2015]约数个数和</a>

> [\[SDOI2015\]约数个数和](https://www.luogu.com.cn/problem/P3327)

> $T$ 组测试数据,给定 $n,m$,求
> $$\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)$$
> 其中 $d(x)=\sum\limits_{k|x}$。

> 数据范围:$1\le n,m,T\le 5\times 10^4$。

---

$n\le m$:

$$
\begin{split}
g(n,m)=&\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)\\
=&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1]\\
=&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}\sum\limits_{k|\gcd(x,y)}\mu(k)\\
=&\sum\limits_{x=1}^n\sum\limits_{y=1}^m\sum\limits_{i=1}^n[x|i]\sum\limits_{j=1}^m[y|j]\sum\limits_{k|\gcd(x,y)}\mu(k)\\
=&\sum\limits_{x=1}^n\sum\limits_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\sum\limits_{k|\gcd(x,y)}\mu(k)\\
=&\sum\limits_{k=1}^n\mu(k)\sum\limits_{x=1}^n[k|x]\sum\limits_{y=1}^m[k|y]\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\\
=&\sum\limits_{k=1}^n\mu(k)\sum\limits_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{kx}\rfloor\lfloor\frac{m}{ky}\rfloor\\
=&\sum\limits_{k=1}^n\mu(k)\sum\limits_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{\lfloor\frac{n}{k}\rfloor}{x}\rfloor\lfloor\frac{\lfloor\frac{m}{k}\rfloor}{y}\rfloor\\
\end{split}
$$

设整除分块函数 $\operatorname{fenk}(n)=\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor$。

所以上式

$$
\begin{split}
=&\sum\limits_{k=1}^n\mu(k)\operatorname{fenk}(\lfloor\frac{n}{k}\rfloor)\operatorname{fenk}(\lfloor\frac{m}{k}\rfloor)\\
\end{split}
$$

然后分块套分块,加个莫比乌斯前缀和,即可。

 <details>
<summary>Code</summary>
```cpp
#include <bits/stdc++.h>
using namespace std;

//&Start
#define lng long long
#define lit long double
#define kk(i,n) "\n "[i<n]
const int inf=0x3f3f3f3f;
const lng Inf=1e17;

//&Mobius
const int N=5e4;
bitset<N+10> np;
int p[N+10],cnt,mu[N+10];
void Mobius(){
	mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!np[i]) p[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*p[j]<=N;j++){
			np[i*p[j]]=1;
			if(i%p[j]==0){mu[i*p[j]]=0;break;}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=2;i<=N;i++) mu[i]+=mu[i-1];//莫比乌斯前缀和
}

//&Fenk
lng fk[N+10];
lng Fenk(int n){//fenk函数
	lng res=0;
	for(int l=1,r;l<=n;l=r+1)
		r=n/(n/l),res+=1ll*(r-l+1)*(n/l);
	return res;
}

//&Data
int t,n,m;

//&Main
int main(){
	Mobius();
	for(int i=1;i<=N;i++)
		fk[i]=Fenk(i);
	scanf("%d",&t);
	for(int ti=1;ti<=t;ti++){
		scanf("%d%d",&n,&m);
		if(n>m) n^=m^=n^=m;
		lng ans=0;
		for(int l=1,r;l<=n;l=r+1){//外层大分块
			r=min(n/(n/l),m/(m/l));
			ans+=fk[n/l]*fk[m/l]*(mu[r]-mu[l-1]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

</details>


如果有感悟或经验,后期会更新,感谢支持。

祝大家学习愉快!

原文出处:https://www.cnblogs.com/Wendigo/p/12441788.html

展开阅读全文
mu
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部