[HAOI2011]Problem b [莫比乌斯反演]

本文主要是介绍[HAOI2011]Problem b [莫比乌斯反演]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

很明显类似矩阵前缀和一样查4次 , 然后就是莫比乌斯反演模板了

---

#include<bits/stdc++.h>
#define N 50050
#define LL long long
using namespace std;
int mu[N],p[N],tot,isp[N],s[N],a,b,c,d,k;
LL Q(int n,int m,int k){if(n>m) swap(n,m); n/=k; m/=k;LL ans = 0;for(int l=1,r;l<=n;l=r+1){int x1=n/l,x2=m/l;r = min(n/x1,m/x2);ans += (LL)(s[r]-s[l-1]) * x1 * x2;	} return ans;	
}
int main(){mu[1]=s[1]=1;for(int i=2;i<=N-50;i++){if(!isp[i]) mu[i]=-1,p[++tot]=i;for(int j=1;j<=tot;j++){if(p[j]*i>N-50) break;isp[p[j]*i]=1;if(i%p[j]==0) break;mu[p[j]*i] = -mu[i];}s[i] = s[i-1] + mu[i];}int T; scanf("%d",&T); while(T--){scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);printf("%lld\n",Q(b,d,k) - Q(a-1,d,k) - Q(b,c-1,k) + Q(a-1,c-1,k));}return 0;
}

 

这篇关于[HAOI2011]Problem b [莫比乌斯反演]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---