这道题是欧拉函数的使用，这里简要介绍下欧拉函数。

　　欧拉函数定义为：对于正整数n,欧拉函数是指不超过n且与n互质的正整数的个数。

　　欧拉函数的性质：1.设n = p₁^a1p₂^a2p₃^a3p₄^a4...p_k^ak为正整数n的素数幂分解，那么φ(n) = n·(1-1/p₁)·(1-1/p₂)·(1-1/p₃)···(1-1/p_k)

　　　　　　　　　　2.如果n是质数，则φ(n) = n-1;  反之，如果p是一个正整数且满足φ(p)=p-1，那么p是素数。

　　　　　　　　　　3.设n是一个大于2 的正整数，则φ(n)是偶数

　　　　　　　　　　4.当n为奇数时，有φ(2n)=φ(n)

　　　　　　　　　　5.设m和n是互质的正整数，那么φ(mn)=φ(m)φ(n)

（1）可以根据性质1，写出计算欧拉函数值的程序：  复杂度为O(√n)

1 //直接求解欧拉函数 2 int euler(int n){ //返回euler(n)  3      int res=n; 4      for(int i=2;i*i<=n;i++){ 5         if(n%i==0){ 6             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出  7             while(n%i==0) n/=i; 8         } 9      } 10      if(n>1) res=res/n*(n-1);11      return res;12 }

 

（2）上面这种写法中，在for循环中选择i时，是顺序选择的。事实上性质1 中的p_1、p_2、p_3、p_4、...p_k都是质数。如果在选择时，直接选择质数进行判断，那结果会优化很多。

可以先把50000以内的素数用筛法选出来并保存，以方便欧拉函数使用。这样，在不考虑筛法的时间复杂度，而单看欧拉函数，其复杂度变为O(x),x为√n以内素数的个数。

 

1 #include 
     
       2 bool boo[50000];int p[20000]; 3  4 void prim(){ 5     //线性筛素数 6     memset(boo,0,sizeof(boo)); 7     boo[0]=boo[1]=1; 8     int k=0;      9     for(int i=2;i<50000;i++){10         if(!boo[i]) p[k++]=i;11         for(int j=0;j
      
       <50000;j++){12             boo[i*p[j]] = 1;13             count++;14             if(!(i%p[j])) break;15         }16     } 17     18 } 19 20 int phi(int n){21     int rea = n;22     for(int i=0;p[i]*p[i]<=n;i++ ){  //对一些不是素数的可不用遍历   23         if(n%p[i]==0){24             rea = rea-rea/p[i];25             while(n%p[i]==0) n/=p[i];26         }    27     }28     if(n>1) rea-=rea/n;29     return rea;30 }
      
     

 

（3）递推求欧拉函数

　　　　如果频繁的要使用欧拉函数值，就需要预先打表。复杂度约为O(nlnn)

1 //递推法打欧拉函数表    2 #define Max 1000001   3 int phi[Max];   4 void Init(){    5     for(int i=1;i<=Max;i++) phi[i]=i; 6     for(int i=2;i<=Max;i+=2) phi[i]/=2; 7     for(int i=3;i<=Max;i+=2)   8         if(phi[i]==i)   9             for(int j=i;j<=Max;j+=i)  10                phi[j]=phi[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出   11 }

 

 

应用：NYOJ 998   http://acm.nyist.net/JudgeOnline/problem.php?pid=998

这道题的精华如何将符合条件的gcd(x,n)表达出来：见代码  d*Euler(n/d)  中为什么乘以d的解释  。 

然后是遍历一遍小于n的数，测试每个符合的数加起来即可。其实还可以更快，观察发现，在能够整除n的i里面，相对应的n/i也有相似的性质，这样以来只需要遍历到sqrt(n)即可。

网络摘抄代码如下：

1   2 #include
     
       3 #include
      
        4 using namespace std; 5  6 typedef long long LL; 7 LL Euler(LL n){ 8     LL ans = n; 9     for(int i = 2; i * i <= n; i++){10         if(n % i == 0){11             ans = ans / i * (i-1);12             while(n % i == 0)13                 n /= i;14         }15     }16     if(n > 1) ans = ans / n * (n-1);17     return ans;18 }19 20 int main(){    21     LL n,m;22     while(cin>>n>>m){23         LL ans = 0;24         for(int i = 1; i * i <= n; i++){25             if(n % i == 0){26                 if(i >= m){27                     int d = i;28                     ans += d*Euler(n/d);29                     // 考虑 gcd(x,n)  1=
       
        <=n  30                     //这个的由来是  gcd(x/d,n/d) = 1.如果我们取一个能让n/d取整数的d的取值，于是我们31                     //取到了n%i==0的i,于是 能够满足gcd(x,n) = d 的x的个数为Euler(n/d)个32                     //那么在该gcd = d 的情况下需要加到ans里面的d的个数就是Euler(n/d)个 ，所以有ans+=d*Euler(n/d)33                      34                 }35                 if(i * i != n && n / i >= m){36                     int d = n / i;37                     ans += d*Euler(n/d);38                 }39             }40         }41         cout<
        
         <