前言：欧拉函数，一种神奇的乘性函数，今天就来一探究竟。
定义：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler'so totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。（参考百部百科）。
两个常用的定理：欧拉定理：对任何两个互质的正整数a, m(m>=2)有a^φ(m) ≡ 1 (mod m)
费马小定理：当m是质数p时，此式则为：a的(p-1)次方除以p的余数恒等于1
常用性质：
1、phi(1) = 1
2、若n是质数，那么phi(n) = n-1
3、若n是质数x的k次幂，phi(n) = (x-1)*x^(k-1)
4、若m，n互质，那么phi(m*n) = phi(m)*phi(n)
5、若n是奇数，那么phi(2*n) = phi(n)
6、若x，y是质数，且n = x*y，那么phi(n) = (x-1)*(y-1)
7、小于n且与n互质的数的和为：n/2 * phi(n)
部分性质：
1.对于素数p, φ(p)=p-1，对于对两个素数p,q φ（pq）=pq-1欧拉函数是积性函数,但不是完全积性函数.即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立.
2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).
3.除了N=2,φ(N)都是偶数.
4.设N为正整数,∑φ(d)=N (d|N).根据性质2,我们可以在O(sqrt(n))的时间内求出一个数的欧拉函数值.如果我们要求1000000以内所有数的欧拉函数,怎么办.
上面的方法复杂度将高达O(N*sqrt(N)).
算法实现：
1）直接实现（利用欧拉函数的公式直接求解）：
int euler(int n) { int ret = 1,i; for (i = 2;i * i <= n;i++) if (n % i == 0) { n /= i; ret *= (i - 1); while (n % i == 0) { n /= i; ret *= i; } } if (n > 1) ret *= (n - 1); return ret; }
2）素数筛法实现
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=1e5+10; int phi[maxn]; void Euler(){ phi[1]=1; for(int i=2;i<N;i++) phi[i]=i; for(int i=2;i<N;i++) if(phi[i]==i) for(int j=i;j<N;j+=i) phi[j]=phi[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 }
3）超快euler筛法（不会证明）
用到的定理：
p为质数
1. phi(p)=p-1 因为质数p除了1以外的因数只有p，故1至p的整数只有p与p不互质
2. 如果i mod p = 0, 那么 phi(i * p)=phi(i) * p
3.若i mod p ≠0, 那么 phi( i * p )=phi(i) * ( p-1 )
#include<cstdio> using namespace std; const int N = 1e6+10 ; int phi[N], prime[N]; int tot;//tot计数，表示prime[N]中有多少质数 void Euler(){ phi[1] = 1; for(int i = 2; i < N; i ++){ if(!phi[i]){ phi[i] = i-1; prime[tot ++] = i; } for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){ if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1); else{ phi[i * prime[j] ] = phi[i] * prime[j]; break; } } } } int main(){ Euler(); }case：
a和p互质：
p是质数
a与p不互质
