首页 > 代码库 > BZOJ 1101 [POI2007]Zap（莫比乌斯反演）

BZOJ 1101 [POI2007]Zap（莫比乌斯反演）

2024-08-21 09:44:55   222人阅读

 

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1101

 

【题目大意】

　　求[1,n][1,m]内gcd=k的情况

 

【题解】

　　考虑求[1,n][1,m]里gcd=k

　　等价于[1,n/k][1,m/k]里gcd=1

　　考虑求[1,n][1,m]里gcd=1

　　结果为sum(miu[d]*(n/d)*(m/d))

　　预处理O(n^1.5)

　　由于n/d只有sqrt(n)种取值，所以可以预处理出miu[]的前缀和 询问时分段求和

 

【代码】

#include <cstdio>#include <algorithm>const int N=50010;using namespace std;typedef long long ll;int T,a,b,c,d,k;int tot,p[N],miu[N],sum[N],v[N];void mobius(int n){    int i,j;    for(miu[1]=1,i=2;i<=n;i++){        if(!v[i])p[tot++]=i,miu[i]=-1;        for(j=0;j<tot&&i*p[j]<=n;j++){            v[i*p[j]]=1;            if(i%p[j])miu[i*p[j]]=-miu[i];else break;        }    }for(i=1;i<=n;i++)sum[i]=sum[i-1]+miu[i];}ll cal(int n,int m){    ll t=0;    if(n>m)swap(n,m);    for(int i=1,j=0;i<=n;i=j+1)    j=min(n/(n/i),m/(m/i)),t+=(ll)(sum[j]-sum[i-1])*(n/i)*(m/i);    return t;}int main(){    mobius(50000);    scanf("%d",&T);    while(T--){        scanf("%d%d%d",&a,&b,&k);        printf("%lld\n",cal(a/k,b/k));    }return 0;}

　　

BZOJ 1101 [POI2007]Zap（莫比乌斯反演）


联系
我们