欧拉函数

欧拉函数：就是求出在区间[1,n-1]中有m个数与n互质，求出m的值
欧拉函数的求法：如果a1,a2,a3……是n的质因子数，那么
m=n*(1-1/a1)*(1-1/a2)*(1-1/a3)……

注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4

互质：2个数之间只有1是他们的公约数。

①对于质数p，φ(p) = p - 1。注意φ(1)=1.

②欧拉定理：对于互质的正整数a和n，有a^φ(n) ≡ 1 mod n。

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

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

⑤特殊性质：当n为奇数时，φ(2n)=φ(n)

⑥欧拉函数还有这样的性质：

设a为N的质因数，若(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)。

可以拿这道模板题练手：51Nod 1136

欧拉函数模板：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 //求φ(n)
 9 LL phi(LL n){
10     if(n==1) return 1;
11     LL ans=n;
12     for(int i=2;i*i<=n;i++){
13         if(n%i==0){
14             ans=ans*(i-1)/i;            //1-1/p=(p-1)/p
15             while(n%i==0)
16                 n/=i;
17         }
18     }
19     if(n>1)
20        ans=ans*(n-1)/n;
21     return ans;
22 }