欧拉函数，欧拉定理，费马小定理介绍及模板

定理：

1. 如果$n$为某一个素数$p$，则:$\phi(p)=p-1$
2. 如果$n$为某一个素数$p$的幂次$p^a$，则:$\phi(p^a)=(p-1)*p^{a-1}$
3. 如果$n$为任意两个互质的数$a,b$的乘积，则:$\phi(a*b)=\phi(a)*\phi(b)$
4. 设$n=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}$为正整数$n$的素数幂分解，那么
   $$\phi(n)=n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*...*(1-\frac{1}{p_k})$$
   推论: 当$n$为奇数时，有$\phi(2n)=\phi(n)$

以下是两个常用的定理:

• 欧拉定理:对于任何两个数值的正整数$a,m$(m>=2)，有$a^{\phi(m)}\equiv 1(mod\ m)$
• 费马小定理: 当$m$是质数时，$a^{m-1}\equiv1(mod\ m)$

模板

返回小于等于n且与n互质的数的个数

int euler_phi(int n)  
{  int res = n;  int m = (int)sqrt(n);  for(int i = 2; i <= m; i++)  if(n % i == 0)  {  res = res / i * (i-1);  while(n % i == 0) n /= i;  }  if(n > 1) res = res / n * (n-1);  return res;  
}

筛选法求欧拉函数

void euler_phi()  
{  for(int i = 1; i < N; i++) phi[i] = i;  for(int i = 2; i < N; i++)  if(phi[i] == i) //成立说明i是素数for(int j = i; j < N; j += i) //j要从i开始，这样可以处理素数的情况  phi[j] = phi[j] / i * (i-1);  
}