欧拉函数详解

欧拉函数

定义

在[1,n]的范围内所有与n互质的数字的个数。

我们用$\phi (n)$来表示数字n的欧拉函数的值，例如：$\phi (4)=2$，与在[1,4]中与4互质的数字是：1 3，有两个，因此 $\phi (4)=2$

性质

1. 如果n是一个质数：$\phi (n)=n-1$
2. 如果n是一个质数，则存在$n^k$，则$\phi (n^k)=(n-1)\cdot n^{k-1}$
3. 积性函数：如果$gcd(m,n)=1$，则$\phi (mn)=\phi (m)\cdot \phi (n)$

计算公式

根据整数唯一分解定理：$n={\prod }_{i=1}^s{p}_i^{a_i}$，即任何一个正整数都可以分解为若干个质数的$a_i$次幂的连乘积，其中$s$为质因子的个数。

因此：
$\phi (n)={\prod }_{i=1}^s\phi (p_i^{a_i})={\prod }_{i=1}^s(p_i-1)\cdot p_i^{a_i-1}={\prod }_{i=1}^s(1-\frac{1}{p_i})\cdot p_i^{a_i}=n\cdot {\prod }_{i=1}^s\frac{p_i-1}{p_i}$

因此我们可以得到欧拉函数的计算公式： $\phi (n)=n\cdot \frac{p_1-1}{p1}\cdot \frac{p_2-1}{p2}\cdots \frac{p_s-1}{p_s}$

通俗来讲，$n$的欧拉函数值就是$n$对每个质因数分解所得到的质因数进行操作后的连乘积 然后再乘一个 $n$。

因此欧拉函数的值与n和他的质因子有关，与项数无关。

---

求某个数欧拉函数值

根据我们刚才得到的欧拉函数的计算公式，可以得到某个值的欧拉函数的值，我们可以使用试除法来计算

typedef long long ll;
//1. 试除法求欧拉函数：某一个确切的值的欧拉函数
ll fun1(int n){ll phi=n;for (int i=2;1ll*i*i<=n;i++){ //防止溢出if (n%i==0){  //如果是一个质因子phi=phi/i*(i-1); //计算欧拉函数值while (n%i==0){ //分解质因子n/=i;}}}if (n>1){phi=phi/n*(n-1); //最后还剩其自身}return phi;
}

---

线性筛求区域内欧拉函数

如果 $n$ 是质数，则$\phi (n)=n-1$
在线性筛中，一个合数一定是被他的最小质因子筛掉的。假设这个最小质因数是$p_j$，因此一定存在一个 $m=p_j\cdot i$
此时会出现两种情况：

1. 如果 $i$ 能够被 $p_j$ 整除，则 $i$ 一定包含了 $p_j$ 的所有质因子，因此我们可以得到：
   $\phi (m)=m\cdot {\prod }_{k=1}^s{p}_k^{a_k}=p_j\cdot i\cdot {\prod }_{k=1}^s{p}_k^{a_k}=p_j\cdot \phi (i)$
2. 如果 $i$ 不能被 $p_j$ 整除，则 $i$ 与 $p_j$ 一定是互为质数的，因此有以下式子：
   $\phi (m)=\phi (p_j)\cdot \phi (i)=\phi (i)\cdot (p_j-1)$

并且通过这种线性筛，我们可以得到$[1,n]$范围内的所有的数字的欧拉函数。

最后代码如下：

//2. 筛法求欧拉函数：任意范围内的数值
const int N=1e8+10;
int primes[N]; //存储质数
bool vis[N]; 
int phi[N]; //存储每个数字的欧拉哈数
std::vector<int> vec;
void fun2(int n){int cnt=0;for (int i=2;i<=n;i++){if (!vis[i]){primes[++cnt]=i;//质数i的欧拉函数就是i-1phi[i]=i-1;}for (int j=1;1ll*i*primes[j]<=n;j++){int m=i*primes[j];vis[m]=true;if (i%primes[j]==0){phi[m]=phi[i]*primes[j];break; //整除中断}else{phi[m]=phi[i]*(primes[j]-1);}}}
}