BZOJ2818 欧拉函数

题意:求1--n中满足gcd(x,y)的值为质数的数对(x,y)的数目  ( (x,y)和(y,x)算两个 )

sol:

设p[i]是一个质数,那么以下两个命题是等价的:

1.gcd(x,y)=1

2.gcd(x*p[i],y*p[i])=p[i]

eg:gcd(36,25)=1,gcd(36*7,25*7)=7

所以对于1--n的所有质数p[i],求一下1<=x,y<=n/p[i]中所有gcd(x,y)=1的数对的数目即可。

如何求1--r范围内所有互质数对的数目?

考虑欧拉函数φ(x)=1..x中与x互质的数的数目

设x<=y,那么这样就可以求出来了:

for y:= to r do    //1不是质数也不是合数,而且1和任意数的gcd都等于1,应该除去
  ans+=*phi[y]; //(x,y)和(y,x)算两个
ans++; //这是本题的特殊情况:当x==y时,gcd(y,y)的值也是质数

Solve函数是题解里用的,事先累加了所有2*phi[i],速度要快一点点

Reference: http://blog.csdn.net/acdreamers/article/details/8542292

 #include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long
#define MMX 10000010
int phi[MMX],p[MMX];
LL psum[MMX];
bool pr[MMX];
LL nm,ret,n; void calc_phi(int n) //求1--n的欧拉函数,phi[i]
{ //psum[n]:sum of phi[1..n]*2
for (int i=;i<=n;i++)
phi[i]=;
phi[]=;
for (int i=;i<=n;i++)
if (!phi[i])
for (int j=i;j<=n;j+=i)
{
if (!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
psum[]=;
for (int i=;i<=n;i++)
psum[i]=psum[i-]+phi[i]*;
} void isprime(LL n) //求1--n的质数。pr[i]=1 : i is a prime
{
nm=;
memset(pr,true,sizeof(pr));
LL m=sqrt(n+0.5);
pr[]=false;
for (LL i=;i<=m;i++)
if (pr[i])
{
for (LL j=i*i;j<=n;j+=i)
pr[j]=false;
}
for (int i=;i<=n;i++)
if (pr[i])
{
nm++;
p[nm]=i;
}
} LL Solve(int n) //
{
LL ans = ;
for(int i=; i<=nm&&p[i]<=n; i++)
ans += + psum[n/p[i]];
return ans;
} int main()
{
cin>>n;
isprime(n);
calc_phi(n); LL ret=;
for (int i=;i<=nm;i++)
{
int r=n/p[i];
for (int j=;j<=r;j++) //注意1不能包括进去,因为gcd(1,?)恒等于1
ret+=*phi[j];
ret++;
}
cout<<ret<<endl; //cout<<endl<<Solve(n)<<endl;
return ;
}
上一篇:iOS开发--成员变量与属性


下一篇:[Codeforces 750E]New Year and Old Subsequence