首页 > 代码库 > BZOJ 2818: Gcd
BZOJ 2818: Gcd
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 4443 Solved: 1960
[Submit][Status][Discuss]
Description
给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
HINT
hint
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
Source
湖北省队互测
分析:
枚举质数,然后问题转化为了gcd(x,y)=i的数对个数...
我只能想到这里了...QAQ还是我水...交完发现自己的跑的很慢...上榜的都是1s以内跑完的,我跑了5s...
看hzwer的blog发现还有复杂度更低的做法...
以下摘自hzwer的blog...
枚举每个素数,然后每个素数p对于答案的贡献就是(1 ~ n / p) 中有序互质对的个数
而求1~m中有序互质对x,y的个数,可以令y >= x, 当y = x时,有且只有y = x = 1互质,当y > x时,确定y以后符合条件的个数x就是phiy
所以有序互质对的个数为(1 ~ n/p)的欧拉函数之和乘2减1(要求的是有序互质对,乘2以后减去(1, 1)多算的一次)
那么就只需要先筛出欧拉函数再求个前缀和就可以了
巨机啊...还是我太水了TAT...
代码:
1 #include<algorithm> 2 #include<cstring> 3 #include<cstdio> 4 //by NeighThorn 5 using namespace std; 6 //大鹏一日同风起,扶摇直上九万里 7 8 const int maxn=10000000+5; 9 10 int n,cnt,vis[maxn],miu[maxn],prime[maxn]; 11 12 long long ans=0; 13 14 signed main(void){ 15 scanf("%d",&n);miu[1]=1;cnt=0; 16 for(int i=2;i<=10000000;i++){ 17 if(!vis[i]) 18 vis[i]=1,prime[++cnt]=i,miu[i]=-1; 19 for(int j=1;j<=cnt&&prime[j]*i<=10000000;j++){ 20 vis[i*prime[j]]=1; 21 if(i%prime[j]==0){ 22 miu[i*prime[j]]=0;break; 23 } 24 miu[i*prime[j]]=-miu[i]; 25 } 26 } 27 for(int i=2;i<=10000000;i++) 28 miu[i]+=miu[i-1]; 29 for(int i=1;i<=cnt&&prime[i]<=n;i++){ 30 int lala=n/prime[i]; 31 for(int d=1,r;d<=lala;d=r+1){ 32 r=lala/(lala/d); 33 if(r>lala) 34 r=lala; 35 ans+=(long long)(miu[r]-miu[d-1])*(lala/d)*(lala/d); 36 } 37 } 38 printf("%lld\n",ans); 39 return 0; 40 }
By NeighThorn
BZOJ 2818: Gcd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。