一、概念：
在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。
例如φ(8)=4，因为1,3,5,7均和8互质。
欧拉函数用希腊字母φ表示,φ(N)表示N的欧拉函数.
对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1).
（初学者一定注意：此处的欧拉函数与图论中的欧拉回路、欧拉公式不同，欧拉大神这一辈子著作等身啊）。
对于互质的理解：
互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。
互质数具有以下定理：
（1）两个数的公因数只有1的两个非零自然数,叫做互质数；举例：2和3，公因数只有1，为互质数；
（2）多个数的若干个最大公因数只有1的正整数，叫做互质数；
（3）两个不同的质数，为互质数；
（4）1和任何自然数互质。两个不同的质数互质。一个质数和一个合数，这两个数不是倍数关系时互质。不含相同质因数的两个合数互质；
（5）任何相邻的两个数互质；（必为一奇一偶）
（6）任取出两个正整数他们互质的概率（最大公约数为一）为6/π^2。
二、通式：
其中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 ( p为 质数 )，则 φ(n) = p^k-p^(k-1) = (p-1)p^(k-1)，（ 除 p 的倍数外，其他数均为 p 的互质数 ）。
若n = p（ p 为质数），则 φ(n) = p-p^(1-1) = p-1。
三、性质：
(1) p^k型欧拉函数:
若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。
若N是质数p的k次幂(即N=p^k)，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。
(2)mn型欧拉函数
设n为正整数，以φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值。若m,n互质，φ(mn)=(m-1)(n-1)=φ(m)φ(n)。
(3)特殊性质:
若n为奇数时，φ(2n)=φ(n)。
对于任何两个互质 的正整数a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 欧拉定理
当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1)=1 mod n (恒等于)此公式即 费马小定理
四、模板
1.直接求小于或等于n,且与n互质的个数:
1 int eular(int n)
2 {
3 int i,ret=n;
4 for(i=2; i<=sqrt(n); i++)
5 {
6 if(n%i==0)
7 {
8 ret=ret/i*(i-1);///这里先使用除法是为了防止溢出，ret=ret*(1-1/p(1))
9 while(n%i==0)///为了完全消除我们已经除完了刚才得到的那个i因子,确保下一个得到的i是n的素因子
10 {
11 n/=i;
12 }
13 }
14 }
15 if(n>1)///可能还剩下一个素因子没有除
16 {
17 ret=ret/n*(n-1);
18 }
19 return ret;
20 }
2.筛选模板:求[1,n]之间每个数的质因数的个数
如果我们要求的数比较多，如果一个一个求那么很容易就超时，所以我们自然而然就想到——打表。
如果我们依照上述思想，来个最朴素的打表。
1 void euler()
2 {
3 p[1]=1;
4 for(int i=2; i<=MAXN; i++)
5 {
6 int n=i;
7 p[i]=i;
8 for(int j=2; j<=sqrt(n); j++)
9 {
10 if(n%j==0)
11 {
12 p[i]=p[i]/j*(j-1);
13 while(n%j==0)
14 {
15 n=n/j;
16 }
17 }
18 }
19 if(n>1)
20 {
21 p[i]=p[i]/n*(n-1);
22 }
23 }
24 for(int i=2; i 25 { 26 p[i]+=p[i-1]; 27 } 28 } 但是这种打表方法还是不太理想，效率不是太高，下面给出两种改进后的算法。 对于这种打表方法，我开始不是很明白，网络上也没有比较完全的说明，下面给出一些我自己的理解。 之前的打表方式是枚举每个数，再去找每个数的质因子，由于有一些数有相同的质因子，无疑会增大时间复杂度。在这里我们选择去枚举素因子，素因子可是少很多。比如素因子是2，那么我们便能求出那些含有2这个素因子的一些数的欧拉函数，例如2,4,8,10......当然像10,12,20,这样的数不仅仅只含有2这一个素因子，我们先欧拉函数的通式先求出一部分来，之后枚举其他素因子的时候再次计算，也就跳过了if(!euler[j])。同时下次需要枚举的数将会是避开已经求出来或者部分求出来（例如2下的10,12，20）数，作为一个新的素因子再次进入循环。 是不是有点像筛法求素数的思路。。。。 1 #define size 1000001 2 int euler[size]; 3 void Init() 4 { 5 euler[1]=1; 6 for(int i=2; i 7 { 8 if(!euler[i]) 9 { 10 for(int j=i; j 11 { 12 if(!euler[j]) 13 { 14 euler[j]=j; 15 } 16 euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 17 } 18 } 19 } 20 } 好文阅读
发表评论