NYOJ 998

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

　　欧拉函数定义为：对于正整数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 <cstring>
 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<k&&i*p[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<iostream>
 3 #include<cstdio>
 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=<x<=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<<ans<<endl;
42     }
43     return 0;
44 }
45