莫比乌斯反演

莫比乌斯反演

思想：不直接求解，用一个序列把另一个序列表示出来。

定义 f(n)和g(n)是在正整数集合上的两个函数，如果有：

那么：

其中：

若

，那么

若

，任意两个不同

和

的为互异素数，那么

其它:

重点研究mu[]：

10以内：

1 -1 -1 0 -1 1 -1 0 0

在程序设计中的mu[i]就是上面的

与素因子快速筛相关的莫比乌斯求法：

int mu[105],pri[105],cnt;bool vis[105];void getmu(){ mu[1]=1; for(int i=2;i<105;i++){ if(!vis[i]) { pri[cnt++]=i; mu[i]=-1; } for(int j=0;j

简短的莫比乌斯求法：

void getmu(){ for(int i=1;i<105;i++){ int targe=i==1?1:0; int delta=targe-mu[i]; mu[i]=delta; for(int j=2*i;j<105;j+=i) mu[j]+=delta; }}

hdu 1695

​​有多少个(q1,q2)=k，其中q1在(a,b)中，q2在(c,d)中，我们可以假设a=c=1

简单的解法：欧拉函数+容斥原理 分析：设B=b/k;  D=d/k

问题等价于求解有多少（p1，p2)=1，其中p1和p2分别在(1,B)和(1,D)中

我们这样设置，令D>B，对应：q2>q1，这就是欧拉函数。 当q2>B时直接容斥求之。

#include #include using namespace std; //int : 2 + 9个0const int N=1e5+10;typedef long long LL;LL phi[N],pri[N/10],cnt;bool vis[N];void getpri(){ cnt=0; for(LL i=2;i1) fac[top++]=n;}int main(){ //freopen("cin.txt","r",stdin); LL t,a,b,c,d,k,ca=0; get(); getpri(); cin>>t; while(t--){ scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k); if(b>d){ b=b^d; d=b^d; b=b^d; } if(k==0||k>b||k>d) { printf("Case %lld: 0\n",++ca); continue; } b=b/k; d=d/k; LL ans=0; for(int i=1;i<=b;i++){ ans=ans+phi[i]; } for(int i=b+1;i<=d;i++){ solve(i); LL temp=0; for(int j=1;j<(1<

第二种解法：莫比乌斯反演

设：

f(k)是满足(q1,q2)=k的对数。

F(d)是(q1,q2)为k的倍数的对数（其中1<=x<=b,  1<=y<=d)

有：

关于反演的另一种解释（来自ACDREAMER大神）：

推出：

将b和d都除以k处理后，1--d内所有的f(1)求出 ans1

1--b内所有的f(1)求出 ans2

ans2含有ans1中的重复部分（(k1,k2)和(k2,k1)是一样的）

附图说明：

ans=ans1-ans2/2;

#include #include using namespace std; //int : 2 + 9个0const int N=1e5+10;typedef long long LL;LL mu[N],cnt,pri[N];bool vis[N];void getmu(){ cnt=0; mu[1]=1; for(int i=2;i>t; while(t--){ scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k); if(b>d){ b=b^d; d=b^d; b=b^d; } if(k==0||k>b||k>d) { printf("Case %lld: 0\n",++ca); continue; } b=b/k; d=d/k; LL ans1=0,ans2=0; for(int i=1;i<=b;i++) ans1=ans1+(LL)mu[i]*(b/i)*(d/i); for(int i=1;i<=b;i++) ans2=ans2+(LL)mu[i]*(b/i)*(b/i); printf("Case %lld: %lld\n",++ca,ans1-ans2/2); } return 0;}

先写到这里，相信mobius登场后，很多难题会随之而来。。。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。