简介
莫比乌斯反演是数论中的重要内容。对于一些函数 f(n),如果很难直接求出它的值,而容易求出其倍数和或约数和 g(n),那么可以通过莫比乌斯反演简化运算,求得 $ f(n) $ 的值。
符号及规定
1.[P] 是指,当 P 为真时,式子的值是 1;当 P 为假时,式子的值是 0。
2.a∣b 是指 b 被 a 整除,即存在一个整数 k 使得 b=ka。
3.n⊥m 是指 n 与 m 互质,即 gcd(n,m)=1。
积性函数
定义
如果一个数论函数 $ f(n)$ 满足:当 $ x\perp y $ 时,f(xy)=f(x)f(y),则称 f(n) 为 积性函数。
性质
若 f(x) 和 g(x) 均为积性函数,则以下函数也为积性函数:
$$
\begin{aligned}h(x)&=f(x^p)\\
h(x)&=f^p(x)=f(x)^p\\
h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g(\frac{x}{d})\end{aligned}
$$
证明:两个积性函数的狄利克雷卷积是积性函数
已知 h(n)=f(n)g(n),且 f(n),g(n) 都是积性函数。
由于:若 n⊥m,则每个 nm 的约数都可以分解成一个 n 的约数和一个 m 的约数的积,且若 n⊥m,a⊥n,b⊥m,则 a⊥b。
若 n⊥m,则
$$
\begin{aligned}h(nm) & =\sum_{d\mid nm}f(d)g\left(\frac{nm}d\right) \\ & =\sum_{a\mid n且b\mid m} f(ab)g\left(\frac{nm}{ab}\right) \\ & =\sum_{a\mid n且b\mid m}f(a)f(b)g\left(\frac na\right)g\left(\frac mb\right)\\ & = \left(\sum_{a\mid n} f(a)g\left(\frac na\right)\right)\left(\sum_{b\mid m}f(b)g\left(\frac mb\right)\right) \\ & =h(n)h(m)\end{aligned}
$$
常见积性函数
欧拉函数:φ(n)=i=1∑n[gcd(i,n)=1],表示不大于 n 且与 n 互质的正整数个数。
约数个数函数:d(n)=d∣n∑1=d=1∑n[d∣n],表示 n 的约数的个数。
约数和函数: σ(n)=d∣n∑d=d=1∑n[d∣n]⋅d,表示 n 的各个约数之和。
莫比乌斯函数
完全积性函数
元函数:ϵ(n)=[n=1]
单位函数:id(n)=n,idk(n)=nk
恒等函数:I(n)=1
狄利克雷卷积
定义
定义两个数论函数的 狄利克雷卷积 ∗ :
若 h=f∗g,则
h(n)=i∣n∑f(i)g(in)
即
h(n)=i×j=n∑f(i)g(j)
性质
1. 交换律:$ \mathbf f \ast \mathbf g=\mathbf g \ast \mathbf f $
2. 结合律:$(\mathbf f \ast \mathbf g)\ast \mathbf h=\mathbf f\ast(\mathbf g \ast \mathbf h) $
(i⋅j)⋅k=n∑(f(i)g(j))h(k)=i⋅(j⋅k)=n∑f(i)(g(j)h(k))
3. 分配律:(f+g)∗h=f∗h+g∗h
i⋅j=n∑(f(i)+g(i))∗h(j)=i⋅j=n∑(f(i)h(j)+g(i)h(j))=i⋅j=n∑f(i)h(j)+i⋅j=n∑g(i)h(j)
4.(xf)∗g=x(f∗g)
i⋅j=n∑(x⋅f(i))g(j)=x⋅i⋅j=n∑f(i)g(j)
5.单位元:ϵ∗f=f,其中 ϵ(n)=[n=1]={10n=1n>1
6.逆元:对每个 f(1)=0 的函数 f,都存在一个函数 g 使得 f∗g=ϵ
如何求出一个函数的逆?
定义:
g(n)=f(1)1[n=1]−i∣n,i=1∑f(i)g(in)
则
$
\begin{aligned}&\quad\sum_{i\mid n}\mathbf f(i)\mathbf g\left(\frac ni\right) \\ & =\mathbf f(1)\mathbf g(n)+\sum_{i\mid n,i\neq1}\mathbf f(i)\mathbf g\left(\frac ni\right) \\ & =[n=1]\end{aligned}$
常用结论
$$
\begin{aligned}\epsilon=\mu\ast I&\Longleftrightarrow \epsilon(n)=\displaystyle\sum\limits_{d|n}\mu(d) \\
\mathbf{d}=I\ast I&\Longleftrightarrow \mathbf{d}(n)=\displaystyle\sum\limits_{d|n}1 \\
\sigma=\mathbf{id}\ast I&\Longleftrightarrow \sigma(n)=\displaystyle\sum\limits_{d|n}d \\
\varphi=\mu\ast\mathbf{id}&\Longleftrightarrow\varphi(n)=\displaystyle\sum\limits_{d|n}d·\mu(\frac{n}{d})
\end{aligned}
$$
莫比乌斯函数
定义
μ 为莫比乌斯函数,定义为:
$$
\mu(n)=\begin{cases}1 & n=1 \\ (-1)^k & k\ 为 \ n\ 的不同质因子个数 \\ 0 & n\ 含有平方因子 \end{cases}
$$
通俗的讲,当 n 包含相等的质因子时,μ(n)=0,当 n 的所有质因子各不相等时,若 n 有偶数个质因子,μ(n)=1,若 n 有奇数个质因子,μ(n)=−1。
性质
莫比乌斯函数是积性函数,还有如下性质:
$$
\displaystyle\sum\limits_{d|n}\mu(d)=\begin{cases}1 & n=1\\0 & n\neq 1 \end{cases}
$$
即 d∣n∑μ(d)=ϵ(n),即 μ∗I=ϵ
证明:
设 n=i=1∏kpici,n′=i=1∏kpi
则d∣n∑μ(d)=d∣n′∑μ(d)=i=0∑kCki⋅1k−i⋅(−1)i=(1+(−1))k
根据二项式定理,易知该式在 k=0 即 n=1 时值为 1,否则为 0。这也同时证明了 d∣n∑μ(d)=[n=1]=ϵ(n) 以及 μ∗I=ϵ。
补充结论
[gcd(i,j)=1]⟺d∣gcd(i,j)∑μ(d)
线性筛
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| void get_mu() { mu[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; mu[i]=-1; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } mu[i*prime[j]]=-mu[i]; } } }
|
莫比乌斯反演
定理
设 F(n),f(n) 为两个数论函数,如果有:
F(n)=d∣n∑f(d)
那么有:
f(n)=d∣n∑μ(d)F(dn)
证明
方法一:对原式做数论变换
$$
\begin{aligned}&\displaystyle\sum\limits_{d|n}\mu(d)F(\frac{n}{d})\\
=&\displaystyle\sum\limits_{d|n}\mu(d)\sum\limits_{k|\frac{n}{d}}f(k)\\
=&\displaystyle\sum\limits_{d|n}\displaystyle\sum\limits_{k|\frac{n}{d}}\mu(d)f(k)\\
=&\sum\limits_{kd|n}\mu(d)f(k)(k|n\ 且\ d|n才会对答案产生贡献,即\ kd|n)\\
=&\displaystyle\sum\limits_{k|n}\sum\limits_{d|\frac{n}{k}}\mu(d)f(k)\\
=&\sum\limits_{k|n}f(k)\sum\limits_{d|\frac{n}{k}}\mu(d)\\
=&f(n)\end{aligned}
$$
用 d∣n∑f(d) 来替换 F(dn),再变换求和顺序。
最后一步变换的依据:d∣n∑μ(d)=[n=1],因此当 kn=1 时,第二个和式才为 1。
此时 n=k,故原式等价于 k∣n∑[n=k]⋅f(k)=f(n)。
方法二:利用卷积
原问题为:已知 F=f∗I,证明 f=F∗μ。
易知如下转化:F∗μ=f∗I∗μ=f∗ϵ=f。
如果 g=f∗I,就有 f=f∗I∗μ=g∗μ。
也就是说,如果 g(n)=d∣n∑f(d),有 f(n)=d∣n∑μ(dn)g(d)。
类似的,可以发现 idk 的逆是 t=μ(n)nk,如果
g(n)=d∣n∑(dn)kf(d)
有
f(n)=d∣n∑μ(dn)(dn)kg(d)
比如,φ=μ∗id,也就是
φ(n)=d∣n∑μ(dn)d
证明 $\varphi(n)=\displaystyle\sum\limits_{d|n}d·\mu(\frac{n}{d}) $
已知 d∣n∑φ(d)=n,表示成狄利克雷卷积的形式:φ∗I=id
φ∗I=id⟹φ∗I∗μ=id∗μ⟹φ∗ϵ=id∗μ
即 φ=id∗μ⟶φ(n)=d∣n∑μ(d)⋅dn。
上式两边同时除以 n,得到 nφ(n)=d∣n∑dμ(d)。
例题
洛谷 P2257 YY的GCD
题目描述
计算
i=1∑Nj=1∑M[gcd(i,j)∈prime]
多组询问,每组 N,M≤107,数据组数 T=104。 gcd(i,j)=n=2(N=4,M=6)
分析
设 f(d) 为 gcd(i,j)=d 的个数,F(n) 为 gcd(i,j)=n 和 gcd(i,j)=n 的倍数的个数。
f(d)=i=1∑nj=1∑m[gcd(i,j)=d],F(n)=n∣d∑f(d)=⌊nN⌋⌊nM⌋
则
f(n)=n∣d∑μ(nd)F(d)
考虑枚举所有质数 p:
ans=p∈prime∑i=1∑nj=1∑m[gcd(i,j)=p]=p∈prime∑f(p)
进行莫比乌斯反演:
ans=p∈prime∑p∣d∑μ(pd)F(d)
更换枚举项,改为枚举 pd
ans=p∈prime∑d=1∑min(⌊pN⌋,⌊pM⌋)μ(d)F(dp)=p∈prime∑d=1∑min(⌊pN⌋,⌊pM⌋)μ(d)⌊dpN⌋⌊dpM⌋
设 T=dp
ans=T=1∑min(N,M)p∣T,p∈prime∑μ(⌊pT⌋)⌊TN⌋⌊TM⌋=T=1∑min(N,M)⌊TN⌋⌊TM⌋(p∣T,p∈prime∑μ(⌊pT⌋))
⌊TN⌋⌊TM⌋ 可以整除分块,后面的式子可以在筛法后枚举每个质数,再枚举 ⌊pT⌋ 来统计,最后做一个前缀和即可。
代码
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
| #include <iostream> #include <cstdio> using namespace std; const int n=10000010; long long sum[n]; bool vis[n]; int prime[n],mu[n],g[n],cnt; void get_mu(int n) { mu[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; mu[i]=-1; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) break; else mu[i*prime[j]]=-mu[i]; } } for(int j=1;j<=cnt;j++) for(int i=1;i*prime[j]<=n;i++) g[i*prime[j]]+=mu[i]; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+1ll*g[i]; } int main() { get_mu(10000000); int T; cin>>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;l<=N;l=r+1) { r=min(N/(N/l),M/(M/l)); ans=ans+1ll*(N/l)*(M/l)*(sum[r]-sum[l-1]); } printf("%lld\n",ans); } return 0; }
|