首页 > 代码库 > 2818: Gcd
2818: Gcd
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 4488 Solved: 1984
[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
【题解】:
gcd(a,b)=p 则 gcd(a/p,b/p)=1;
设 a<=b 则gcd(a,b)=phi[b](与b互质的个数)
所以只需要枚举每一个素数,每一个数(这里可以用n的前缀和来维护,记为sum[n])求解出ans=Σf[n/prime[i]]*2-1(考虑a>b,并减去(1,1)之类的值)
【代码】:
#include<cstdio>using namespace std;const int N=1e7+10;int n,tot,phi[N],prime[N];long long sum[N],ans;bool check[N]={1,1};void prepare(){ phi[1]=0; for(int i=2;i<=n;i++){ if(!check[i]) prime[++tot]=i,phi[i]=i-1; for(int j=1;j<=tot&&i*prime[j]<=n;j++){ check[i*prime[j]]=1; if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1); else {phi[i*prime[j]]=phi[i]*prime[j];break;} } }}int main(){ scanf("%d",&n);prepare();sum[1]=1; for(int i=2;i<=n;i++) sum[i]=sum[i-1]+phi[i]*2; for(int i=1;i<=tot;i++) if(prime[i]<n) ans+=sum[n/prime[i]]; printf("%lld",ans); return 0;}
2818: Gcd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。