參考：http://blog.csdn.net/leolin_/article/details/6642096

歐拉函數(shù)：對于一個正整數(shù)n，小于n且和n互質(zhì)的正整數(shù)（包括1）的個數(shù)，記作φ(n) 。

通式：φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中p1, p2……pn為x的所有質(zhì)因數(shù)，x是不為0的整數(shù)。φ(1)=1（唯一和1互質(zhì)的數(shù)就是1本身）。

對于質(zhì)數(shù)p，φ(p) = p - 1。注意φ(1)=1.

歐拉定理：對于互質(zhì)的正整數(shù)a和n，有aφ(n) ≡ 1 mod n。

歐拉函數(shù)是積性函數(shù)——若m,n互質(zhì)，φ(mn)=φ(m)φ(n)。

                                 若n是質(zhì)數(shù)p的k次冪，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因為除了p的倍數(shù)外，其他數(shù)都跟n互質(zhì)。

特殊性質(zhì)：當n為奇數(shù)時，φ(2n)=φ(n)

歐拉函數(shù)還有這樣的性質(zhì)：

設(shè)a為N的質(zhì)因數(shù)，若(N % a == 0 && (N / a) % a == 0) 則有E(N)=E(N / a) * a；若(N % a == 0 && (N / a) % a != 0) 則有：E(N) = E(N / a) * (a - 1)。

模板：

long long Euler(long long n) {       long long ans = n, i;       for(i = 2; i*i <= n; ++i) {        if(n%i == 0){            ans = ans - ans/i;            while(n%i == 0)n /= i;        }       }       if(n > 1) {        ans = ans - ans / n;       }       return ans;}