Bzoj 2820: YY的GCD(莫比乌斯反演+除法分块)

2019-11-06 06:49:49

字体：大中小

来源：转载

供稿：网友

2820: YY的GCD Time Limit: 10 Sec Memory Limit: 512 MB Description 神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种傻×必然不会了，于是向你来请教……多组输入 Input 第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M Output T行，每行一个整数表示第i组数据的结果 Sample Input 2 10 10 100 100 Sample Output 30 2791 HINT T = 10000 N, M <= 10000000

这里写图片描述 Here 基本上还是看懂了的….

/*莫比乌斯.最后用除法分块..筛莫比乌斯函数部分:显然每个素数直接计算mu[i]=-1.我们知道莫比乌斯函数值是(-1)^k,k是互异质数的个数.对于一个合数x,令它质因子的最小的那个为p1,则有x=p1*t1,另设一个与异于p1的质因子为p2.则有p1*t1=p2*t2.因为p1与p2互素,所以p2|t1,p1|t2.所以当i枚举到t2时,因为p1|t2,所以退出**有一个疑问:就是如果有一个数x1>x,那直接退出以后是不是会影响x1函数值的计算???数学不好没证出来orz**假如有一个x1=t1*p,且p是x1最大的质因数.当i枚举到t1时,计算一下x的函数值.所以我们保证算的每一个合数的莫比乌斯函数的时候都是在最后一个计算素数的时候的即每个函数值都只计算了一次.复杂度是O(n)哒.*/#include<iostream>#include<cstdio>#define MAXN 10000001#define LL long longusing namespace std;int mu[MAXN],PRi[MAXN],tot,g[MAXN],sum[MAXN],last;LL ans,n,m;bool vis[MAXN];void pre(){ mu[1]=1; for(int i=2;i<=MAXN-1;i++) { if(!vis[i]) pri[++tot]=i,mu[i]=-1,g[i]=1; for(int j=1;j<=tot&&i*pri[j]<=MAXN-1;j++) { vis[i*pri[j]]=true; if(i%pri[j]) mu[i*pri[j]]=-mu[i],g[i*pri[j]]=mu[i]-g[i]; else { mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break; } } } for(int i=1;i<=MAXN-1;i++) sum[i]=sum[i-1]+g[i];}int main(){ int t,x,y;pre(); scanf("%d",&t); while(t--) { scanf("%lld%lld",&n,&m); if(n>m) swap(n,m); ans=0; for(LL i=1;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); ans+=(n/i)*(m/i)*(sum[last]-sum[i-1]); } printf("%lld/n",ans); } return 0;}

上一篇：Spring AOP介绍

下一篇：nodejs udp组播通信(未完)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注