BZOJ2818 欧拉函数

时间：2023-11-24 12:49:50

题意：求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 ;

 }

相关文章