首页 > 代码库 > 2818: Gcd

2818: Gcd

2024-08-31 06:56:58   220人阅读

2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 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


联系
我们