首页 > 代码库 > BZOJ 2818 Gcd(莫比乌斯反演)

BZOJ 2818 Gcd(莫比乌斯反演)

 

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

 

【题目大意】

  给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

 

【题解】

  反演简单题。

 

【代码】

#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;const int N=10000010; namespace Mobius{    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;            }        }    }    void cal_sum(){        int j,k;        for(int i=0;i<tot;i++)for(j=k=p[i];j<N;j+=k)sum[j]+=miu[j/k];        for(int i=1;i<N;i++)sum[i]+=sum[i-1];    }    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;    }    void Initialize(int n){        mobius(n);        cal_sum();    }}int n;int main(){    scanf("%d",&n);    Mobius::Initialize(n);    printf("%lld\n",Mobius::Cal(n,n));    return 0;}

BZOJ 2818 Gcd(莫比乌斯反演)