题目描述
给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.
输入格式
一个整数N
输出格式
答案
输入输出样例
输入 #1 复制
4
输出 #1 复制
4
说明/提示
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
思路
对于质数p,满足gcd(i,j)=p的(i,j):
p|i且 p|j,则设i=a,j=b。
即gcd(ap,bp)=p
gcd(a,b)*p=p
gcd(a,b)=1,也就是a、b互质
所以求的就是1<=a,b<=n/p 中满足 gcd(a,b)=1的数字对(a,b)的个数
即phi(1~n/p)
因为这里我们只考虑了a<=b的情况,所以ans * =2;
然后还有phi(a,a)的情况,所以ans-1;
#include<cstdio>
#include<iostream>
#include<algorithm>
const int N=10000005;
long long sum[N],ans;
long long phi[N],prime[N],cnt;
bool is[N];
int main()
{
freopen("1560.in","r",stdin);
freopen("1560.out","w",stdout);
int n,i;
scanf("%d",&n);
sum[1]=phi[1]=1;
for(int i=2;i<=n;++i)
{
if(!is[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
sum[i]=sum[i-1]+phi[i];
for(int j=1;j<=cnt&&prime[j]*i<=n;j++)
{
is[prime[j]*i]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
for(int i=1;i<=cnt;++i)
ans+=sum[n/prime[i]]*2-1;
printf("%lld\n",ans);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)