【学习笔记】莫比乌斯反演(其实只讲(mu))
可能最常见的定义式是这样的:
[F(x)=Sigma_{d|x}f(x) leftrightarrow f(x)=Sigma_{d|x}mu(x)F(x)
\or
\
F(x)=Sigma_{x|d}f(x) leftrightarrow f(x)=Sigma_{x|d}mu(x)F(x)
]
但是这并不是我们(OI)的重点..之前一直学不会这个东西就是因为老研究这个去了(我才不会说是(NOIP)模拟赛有毒瘤出题人以这样的形式让我和莫比乌斯函数见面)
实际上我们喜欢的是这个性质
[Sigma_{d|n}mu(n)=[n=1]
]
假如一个式子里有乘积+约数或者什么什么+布尔值，那就套一下这个公式。
这个式子如何证明：
考虑枚举因数就相当于对于(n=prod p_i^{a_i})选不同的乘起来，你知道当(d)在一个(p_i)中选了超过一的指数，由于此时(exist x^2|n)所以(mu(n)=0)我们就可以不考虑它了。
所以情况只剩下选择不同的(p_i)了，等式就变成了我们选几个不同的素因子:(Sigma C_n^i (-1)^i)，我们直接二项式定理可以得到等式(=(-1+1)^n=0)。
(n=1) 时的证明显然。
( ext{talk is cheap , show me the 例题:})
P2257 YYb的GCD
题意:求:
[Sigma_{i=1}^n Sigma_{j=1}^m [(i,j) in p]
]
(([ ]=lfloor floor))
[=Sigma_{i=1}^n Sigma_{j=1}^m [(i,j) in p]
\
=Sigma_{xin p}Sigma_{i=1}^nSigma_{j=1}^m[(i,j)=x]
\
=Sigma_{xin p}Sigma_{i=1}^{n/d}Sigma_{j=1}^{m/d}[(i,j)=1]
\
=Sigma_{xin p}Sigma_{i=1}^{n/d}Sigma_{j=1}^{m/d}Sigma_{d|(i,j)}mu(d)
\
=Sigma_{xin p}Sigma_{d=1}^{min(m,n)/x}mu(d)[n/dk][m/dk]
\assuem:T=dk
\
=Sigma_{xin p}Sigma_{d=1}^{min(m,n)/x}mu(d)[n/T][m/T]
\
=Sigma_{T=1}^{min(m,n)}[n/T][m/T]Sigma_{xin p,x|T}mu(T/x)
\assume:f(T)=Sigma_{xin p,x|T}mu(T/x)
\
=Sigma_{T=1}^{min(m,n)}[n/T][m/T]f(T)
]
预处理(f(T))数组和他的前缀和，就可以数论分块(O(n^{1.5}))了。
怎么处理(f(T)) 呢？可以考虑先定位一个素数(p)，然后直接(for(i=1 ext{~}1e7))，把所有(f(p imes i)+=mu(i))。复杂度(O(n)?)
#include<bits/stdc++.h>
using namespace std;
inline int qr(){
char c=getchar();
register int ret=0,f=0;
while(not isdigit(c)) f|=c==45,c=getchar();
while( isdigit(c)) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=1e7+5;
typedef long long ll;
bool usd[maxn];
int mu[maxn];
int f[maxn];
ll sum[maxn];
vector < int > pr;
#define pb push_back
inline void gen_mu(){
mu[1]=usd[1]=1;
for(int t=2;t< maxn;++t){
if(not usd[t]) pr.pb(t),mu[t]=-1;
for(auto i:pr)
if(1ll*i*t>=maxn) break;
else if(usd[i*t]=1,t%i) mu[t*i]=-mu[t];
else break;
}
for(auto i:pr)
for(int t=1;1ll*i*t< maxn;++t)
f[i*t]+=mu[t];
for(int t=1;t< maxn;++t) sum[t]=sum[t-1]+1ll*f[t];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
ll ans=0;
gen_mu();
for(int T=qr(),n,m;T;T--,ans=0){
n=qr();m=qr();
if(n>m) swap(n,m);
for(int l=1,r;l<=n;l=r+1)
r=min(n/(n/l),m/(m/l)),ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
if(not ans) puts("0");
else printf("%lld
",ans);
}
return 0;
}
[P3327 SDOI2015]约数个数和
先给个式子
(d(ij)=Sigma_{x|i}Sigma_{y|j}[(x,y)=1])
继续
[=Sigma_i^n Sigma_j^md(ij)
\
=Sigma_i^n Sigma_j^mSigma_{x|i}Sigma_{y|j}[(x,y)=1]
\
=Sigma_i^n Sigma_j^mSigma_{x|i}Sigma_{y|j}Sigma_{d|(x,y)}mu(d)
\
=Sigma_i^n Sigma_j^mSigma_{x|i}Sigma_{y|j}Sigma_{d=1}^{min(m,n)}mu(d) imes [d|(x,y)]
\
=Sigma_{d=1}^{min(m,n)}mu(d)Sigma_i^n Sigma_j^mSigma_{x|i}Sigma_{y|j}[d|(x,y)]
\
=Sigma_{d=1}^{min(m,n)}mu(d)Sigma_x^n Sigma_y^m lfloor frac n x
floorlfloor frac m y
floor[d|(x,y)]
\
=Sigma_{d=1}^{min(m,n)}mu(d)Sigma_x^{lfloor frac n d
floor} lfloor frac n {dx}
floorSigma_y^{lfloor frac m d
floor} lfloor frac m {dy}
floor
]
右边有两个(floor)，可以数论分块。分块后可以直接乘上一段(mu)的前缀和。
#include<bits/stdc++.h>
using namespace std; typedef long long ll;
template < class ccf > inline ccf qr(ccf ret){ret=0;
register char c=getchar();
while(c<48||c>57) c=getchar();
while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
return ret;
}inline int qr(){return qr(1);}
#define pb push_back
const int maxn=5e4+5;
bool usd[maxn];
int mu[maxn];
int sum[maxn];
ll pre[maxn];
vector < int > pr;
inline void gen_mu(){
mu[1]=usd[1]=1;
for(register int t=2;t< maxn;sum[t]=sum[t-1]+mu[t],++t){
if(not usd[t]) mu[t]=-1,pr.pb(t);
for(auto i:pr)
if(1ll*i*t>=maxn) continue;
else if(usd[i*t]=1,t%i) mu[i*t]=-mu[t];else break;
}
for(register ll t=1;t< maxn;++t)
for(register ll l=1,r;l<=t;l=r+1)
r=t/(t/l),pre[t]+=1ll*(r-l+1)*(t/l);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
gen_mu();
for(register int T=qr(),n,m;T;T--){
n=qr(1);m=qr(1);ll ans=0;
for(register ll l=1,r,edd=min(m,n);l<=edd;l=r+1)
r=min(n/(n/l),m/(m/l)),
ans+=1ll*(0ll+sum[r]-sum[l-1])*pre[n/l]*pre[m/l];
printf("%lld
",ans);
}
return 0;
}