首页 > 代码库 > 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(莫比乌斯反演)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。