数论知识总结-莫比乌斯反演
NOIP爆零の蒟蒻又来学数论辣
用yyb的博客学了一下莫比乌斯反演
莫比乌斯函数
玄学
[ mu(x)=left{
egin{aligned}
1 & (x=1) \
0 & (x=p^2 imes k,kin {mathbb{Z}^+}) \
(-1)^k & (x=Pi_{i=1}^{n}{p_i^{k_i}},k_i=1) \
end{aligned}
ight.
]
x=1时，(mu(x)=1)
x包含质数的平方时，(mu(x)=0)
否则令k=x的质因子个数，(mu(x)=(-1)^k)
莫比乌斯反演
有两种形式？？
如果有两个函数(f(x),g(x))：
若满足(g(x)=sum_{d|x}f(d))，就能推出(f(x)=sum_{d|x}mu(frac{x}{d})g(d))
若满足(g(x)=sum_{x|d,dle n}f(d))，就能推出(f(x)=sum_{x|d,dle n}mu(frac{d}{x})g(d))
如果求不出(f(x))，但能快速求出(g(x))，任意一个(f(x))就可以快速算出来。
证明不会嗷嗷嗷嗷嗷嗷，能背就好辣
例题
[POI2007]ZAP-Queries
将a/=d,b/=d，问题转化为求gcd(i,j)=1的对数
设(f(x))为满足(gcd(i,j)=x)的有序数对((i,j))数量，
(F(x))为(gcd(i,j))为(x)倍数的有序数对((i,j))数量。
关系式：(F(x)=sum_{x|d,dle n}f(d))。
现在要求(f(1))
(F(x))很好求，(F(x)=lfloorfrac{a}{x} floor imeslfloorfrac{b}{x} floor)
so (f(x)=sum_{x|d,dle n}mu(frac{d}{x})F(d))
这样枚举可以获得70分的好成绩
好像还有个东西叫数论分块
(F(x))可以分成很多值相等的段，而且最多(O(sqrt{n}))段
于是就可以做了
如果求无序数对的话可以写个solve函数，ans=solve(a,b)-solve(min(a,b),min(a,b))/2
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
#define int long long
using std::min;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=50001;
int mu[maxn],Mu[maxn],pr[maxn],g[maxn];
bool flg[maxn];
main(){
mu[1]=1;
for(rg int i=2;i<maxn;++i){
if(!flg[i])pr[++pr[0]]=i,mu[i]=-1;
for(rg int j=1;i*pr[j]<maxn&&j<=pr[0];++j){
flg[i*pr[j]]=1;
if(i%pr[j]==0){mu[i*pr[j]]=0;break;}
mu[i*pr[j]]=-mu[i];
}
}
for(rg int i=1;i<maxn;++i)Mu[i]=mu[i]+Mu[i-1];
int T=gi(),a,b,k,ans,i,j;
for(rg int zsy=1;zsy<=T;++zsy){
a=gi(),b=gi(),k=gi();
if(k==0){puts("0");continue;}
a/=k,b/=k;ans=0;i=1;
while(i<=min(a,b)){
j=min(a/(a/i),b/(b/i));
ans+=(Mu[j]-Mu[i-1])*(a/j)*(b/j);
i=j+1;
}
printf("%lld
",ans);
}
return 0;
}
[蛤OI2011]Problem B
和上面一样，简单利用容斥。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
using namespace std;
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=50001;
int mu[maxn],Mu[maxn],pr[maxn];
bool yes[maxn];
il ll solve(int x,int y,int k){
if(x==0||y==0)return 0;
if(x>y)swap(x,y);
x/=k,y/=k;
int i=1,j;
ll ret=0;
while(i<=x){
j=min(x/(x/i),y/(y/i));
ret+=1ll*(Mu[j]-Mu[i-1])*(x/j)*(y/j);
i=j+1;
}
return ret;
}
main(){
mu[1]=1;
for(rg int i=2;i<maxn;++i){
if(!yes[i])pr[++pr[0]]=i,mu[i]=-1;
for(rg int j=1;i*pr[j]<maxn&&j<=pr[0];++j){
yes[i*pr[j]]=1;
if(i%pr[j]==0){mu[i*pr[j]]=0;break;}
mu[i*pr[j]]=-mu[i];
}
}
for(rg int i=1;i<maxn;++i)Mu[i]=Mu[i-1]+mu[i];
int T=gi(),a,b,c,d,k;
while(T--){
a=gi(),b=gi(),c=gi(),d=gi(),k=gi();
printf("%lld
",solve(b,d,k)-solve(b,c-1,k)-solve(a-1,d,k)+solve(a-1,c-1,k));
}
return 0;
}
长期更新