首页 > 代码库 > bzoj 2818: Gcd
bzoj 2818: Gcd
2818: Gcd
http://www.lydsy.com/JudgeOnline/problem.php?id=2818
Time Limit: 10 Sec Memory Limit: 256 MBDescription
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
Sample Output
HINT
hint
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
Source
湖北省队互测
gcd(x,y)=p，则gcd（x/p，y/p）=1
法一：欧拉函数
枚举每个素数p，那么该素数p对答案的贡献为[1,n/p]中的有序互质对的个数
求[1,m]中有序互质对（i，j）的个数：
令j>=i
当i=j时，只有i=j=1互质；
当i<j时，确定j后，互质的个数为φ（j）；
所以[1,m]中有序互质对个数=（Σ φ（j））*2-1
j
所以，欧拉筛筛出欧拉函数，求前缀和sum
ans= Σ sum[n/p]*2-1
p为素数，p<=n
耗时：980ms
#include<cstdio>#define N 10000001int prime[N],cnt,phi[N];long long ans,sum[N];bool v[N];int n;void euler(){ phi[1]=1; for(int i=2;i<=n;i++) { if(!v[i]) { prime[++cnt]=i; v[i]=true; phi[i]=i-1; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>n) break; v[prime[j]*i]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } }}int main(){ scanf("%d",&n); euler(); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i]; for(int i=1;i<=cnt;i++) ans+=sum[n/prime[i]]*2-1; printf("%lld",ans);}
法二、莫比乌斯函数
枚举每个素数p，那么该素数p对答案的贡献为[1,n/p]中的有序互质对的个数
求[1,m]中有序互质对（i，j）的个数：
推个式子
n m
Σ Σ [gcd(a,b)]
a=1 b=1
= Σ Σ e（gcd(a,b)）
a=1 b=1
= Σ Σ 1*μ（gcd(a,b)）
a=1 b=1
= Σ Σ Σ μ（d）
a=1 b=1 d\gcd(a,b)
= Σ Σ Σ μ（d）
d d\a ’ d\b ’
=Σ μ（d）floor（n/d）floor（m/d）
d
注：[n]表示若n=1，[n]=1，否则[n]=0
floor表示下取整
所以枚举每个素数p，
对每个素数p，都求一个si=Σ μ（j）floor（n/p/j）floor（n/p/j）
j
素数个数
ans=Σ si
i
耗时：2720ms
#include<cstdio>#define N 10000001using namespace std;bool v[N];int n,cnt;long long ans,prime[N],mul[N];void mobius(){ mul[1]=1; for(int i=2;i<=n;i++) { if(!v[i]) { v[i]=true; prime[++cnt]=i; mul[i]=-1; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>n) break; v[prime[j]*i]=true; if(i%prime[j]==0) { mul[i*prime[j]]=0; break; } else mul[i*prime[j]]=-mul[i]; } }}int main(){ scanf("%d",&n); mobius(); for(int i=1;i<=cnt;i++) for(int j=1;j<=n/prime[i];j++) ans+=mul[j]*(n/prime[i]/j)*(n/prime[i]/j); printf("%lld",ans);}
bzoj 2818: Gcd