[POI2007]ZAP-Queries [莫比乌斯反演]

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

传送门

对于本题 (一下来源于luogu题解)

 

 然后求一个mu的前缀和 , 整除分块搞一下

---

#include<bits/stdc++.h>
#define N 50051
#define LL long long
using namespace std;
int mu[N],prim[N],isp[N],s[N],T,tot;
void Init(){mu[1] = s[1] = 1;for(int i=2;i<=N-50;i++){if(!isp[i]){prim[++tot]=i;mu[i] = -1;}for(int j=1;j<=tot;j++){if(prim[j]*i >= N-50) break;isp[prim[j]*i] = 1;mu[prim[j]*i] = -mu[i];if(i%prim[j]==0){mu[prim[j]*i]=0; break;}}s[i] = s[i-1] + mu[i];}
}
void Solve(){int n,m,d; scanf("%d%d%d",&n,&m,&d);if(n>m) swap(n,m); n/=d; m/=d;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;}printf("%lld\n",ans);
}
int main(){scanf("%d",&T); Init();while(T--) Solve(); return 0;
}

 

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

---