数论知识(2)-------------欧拉函数

欧拉函数：一个整数n，小于且和n互质的正整数的个数（包含1）的个数，用φ(n)表示。

完全余数集合:欧拉函数中与n互质的数字的集合.

~~~~~~~~~~~~~~

性质：

如果n是素数，则 φ(n)=n-1；

求一个数n的所有互素和 sum=φ(n)*n/2; <==这个性质，很有用。

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

费马定理：
若正整数 a 与素数 p 互质，则有 ap - 1 ≡ 1 mod p 。
证明这个定理非常简单，由于 φ(p) = p -1，代入欧拉定理即可证明。

~~~~~~~~~~~~~~~~~~~~~~

补充欧拉公式：

1. pk 的欧拉函数

对于给定的一个素数 p ， φ(p) = p -1。则对于正整数 n = pk ，

φ(n) = pk - pk -1

2. p * q 的欧拉函数

假设 p, q是两个互质的正整数，则 p * q 的欧拉函数为

φ(p * q) = φ(p) * φ(q) ， gcd(p, q) = 1 。

3.任意正整数的欧拉函数

φ(n) =n*(1-1/k1)*(1-1/k2)*......*(1-1/km);

k1,k2...km是n的素数因子

________________________________________

欧拉单点求值

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

欧拉函数打表

 1 void Euler() //欧拉打表。
 2 {
 3     int i,j;
 4     for(i=2;i<=3000000;i++)
 5     opl[i]=i;
 6     opl[1]=0;
 7 
 8     for(i=2;i<=3000000;i++)
 9     if(s[i]==false)
10     {
11         for(j=i;j<=3000000;j=j+i)
12         {
13             opl[j]=opl[j]/i*(i-1);
14             s[j]=true;
15         }
16     }
17 }

还有一种是素数和欧拉表分开的，速度更快。在欧拉题目里有。