首页 > 代码库 > BZOJ2818 欧拉函数

BZOJ2818 欧拉函数

2024-08-01 22:15:11   221人阅读

题意：求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:=2 to r do　　　　//1不是质数也不是合数，而且1和任意数的gcd都等于1，应该除去　　ans+=2*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

 1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 using namespace std; 5 #define LL long long 6 #define MMX 10000010 7 int phi[MMX],p[MMX]; 8 LL psum[MMX]; 9 bool pr[MMX];10 LL nm,ret,n;11 12 void calc_phi(int n)        //求1--n的欧拉函数，phi[i]13 {                           //psum[n]:sum of phi[1..n]*214     for (int i=2;i<=n;i++)15         phi[i]=0;16     phi[1]=1;17     for (int i=2;i<=n;i++)18         if (!phi[i])19             for (int j=i;j<=n;j+=i)20             {21                 if (!phi[j])    phi[j]=j;22                 phi[j]=phi[j]/i*(i-1);23             }24     psum[1]=0;25     for (int i=2;i<=n;i++)26         psum[i]=psum[i-1]+phi[i]*2;27 }28 29 void isprime(LL n)     //求1--n的质数。pr[i]=1 : i is a prime30 {31     nm=0;32     memset(pr,true,sizeof(pr));33     LL m=sqrt(n+0.5);34     pr[1]=false;35     for (LL i=2;i<=m;i++)36         if (pr[i])37         {38             for (LL j=i*i;j<=n;j+=i)39                 pr[j]=false;40         }41     for (int i=1;i<=n;i++)42         if (pr[i])43         {44             nm++;45             p[nm]=i;46         }47 }48 49 LL Solve(int n)     //50 {51     LL ans = 0;52     for(int i=1; i<=nm&&p[i]<=n; i++)53         ans += 1 + psum[n/p[i]];54     return ans;55 }56 57 int main()58 {59     cin>>n;60     isprime(n);61     calc_phi(n);62 63     LL ret=0;64     for (int i=1;i<=nm;i++)65     {66         int r=n/p[i];67         for (int j=2;j<=r;j++)  //注意1不能包括进去，因为gcd(1,?)恒等于168             ret+=2*phi[j];69         ret++;70     }71     cout<<ret<<endl;72 73     //cout<<endl<<Solve(n)<<endl;74     return 0;75 }

 

BZOJ2818 欧拉函数


联系
我们