欧拉函数

定义：在​​数论​​​，对​​正整数​​​n，​​欧拉​​​函数是少于或等于n的数中与n​​互质​​​的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、​​φ函数​​​、欧拉​​商数​​​等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和​​拉格朗日定理​​​构成了​​欧拉定理​​的证明。

简介：

φ函数的值 　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1 ​​互质​​的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4

若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。

设n为正整数，以 φ(n)表示不超过n且与n互

素的正整数的个数，称为n的欧拉函数值，这里函数

φ：N→N，n→φ(n)称为欧拉函数。

欧拉函数是 ​​积性函数​​——若m,n互质，φ(mn)=φ(m)φ(n)。

特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。

大神写的博客，原文地址： ​​点击打开链接​​

先来介绍几个与欧拉函数有关的定理：

定理一：设m与n是互素的正整数，那么

定理二：当n为奇数时，有

。

因为2n是偶数，偶数与偶数一定不互素，所以只考虑2n与小于它的奇数互素的情况，则恰好就等于n的欧拉函数值。

定理三：设p是素数，a是一个正整数，那么

关于这个定理的证明用到容斥：

由于

表示小于

与

互素数的正整数个数，所以用

减去与它不互素的数的个数就行了。那么小于

与

不互素数的个数就是p的倍数个数，有

个。所以定理得证。

定理四：设

为正整数n的素数幂分解，那么

这个定理可以根据定理一和定理三证明，其实用到的就是容斥。如果对容斥熟悉，其实完全就可以直接容斥。

定理五：设n是一个正整数，那么

这个其实可以看莫比乌斯反演就明白了。

定理六：设m是正整数，(a,m)=1，则：

是同于方程

的解。

定理七：如果n大于2，那么n的欧拉函数值是偶数。

求欧拉函数值：

​

[cpp]  ​​view plain​​ ​​copy​​ ​​​ ​​​

1. int phi(int n)  
2. {  
3. int i,rea=n;  
4. for(i=2;i*i<=n;i++)  
5.     {  
6. if(n%i==0)  
7.         {  
8.             rea=rea-rea/i;  
9. while(n%i==0)  n/=i;  
10.         }  
11.     }  
12. if(n>1)  
13.         rea=rea-rea/n;  
14. return rea;  
15. }  

利用递推法求欧拉函数值：

算法原理：开始令i的欧拉函数值等于它本身，如果i为偶数，可以利用定理二变为求奇数的。

若p是一个正整数满足

，那么p是素数，在遍历过程中如果遇到欧拉函数值等于自身的情况，那么

说明该数为素数。把这个数的欧拉函数值改变，同时也把能被该素因子整除的数改变。

[cpp]  ​​view plain​​ ​​copy​​ ​​​ ​​​

1. void phi()  
2. {  
3. for(int i=1; i<N; i++)  p[i] = i;  
4. for(int i=2; i<N; i+=2) p[i] >>= 1;  
5. for(int i=3; i<N; i+=2)  
6.     {  
7. if(p[i] == i)  
8.         {  
9. for(int j=i; j<N; j+=i)  
10.                 p[j] = p[j] - p[j] / i;  
11.         }  
12.     }  
13. }  
14. 
    

最后附一下HDU1286的题解便于加深理解： ​​点击打开链接​