欧拉函数

定义

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

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

性质

如果n是一个质数： φ ( n ) = n − 1 \varphi(n)=n-1 φ(n)=n−1

如果n是一个质数，则存在 n k n^k nk，则 φ ( n k ) = ( n − 1 ) ⋅ n k − 1 \varphi(n^k)=(n-1) \cdot n^{k-1} φ(nk)=(n−1)⋅nk−1

积性函数：如果 g c d ( m , n ) = 1 gcd(m,n)=1 gcd(m,n)=1，则 φ ( m n ) = φ ( m ) ⋅ φ ( n ) \varphi(mn)=\varphi(m)\cdot \varphi(n) φ(mn)=φ(m)⋅φ(n)

计算公式

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

因此：
φ ( n ) = ∏ i = 1 s φ ( p i a i ) = ∏ i = 1 s ( p i − 1 ) ⋅ p i a i − 1 = ∏ i = 1 s ( 1 − 1 p i ) ⋅ p i a i = n ⋅ ∏ i = 1 s p i − 1 p i \varphi(n)=\prod_{i=1}^{s} \varphi(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} φ(n)=∏i=1s​φ(piai​​)=∏i=1s​(pi​−1)⋅piai​−1​=∏i=1s​(1−pi​1​)⋅piai​​=n⋅∏i=1s​pi​pi​−1​

因此我们可以得到欧拉函数的计算公式： φ ( n ) = n ⋅ p 1 − 1 p 1 ⋅ p 2 − 1 p 2 ⋯ p s − 1 p s \varphi(n) = n \cdot \frac{p_1-1} {p1} \cdot \frac{p_2-1}{p2} \cdots\frac{p_s-1}{p_s} φ(n)=n⋅p1p1​−1​⋅p2p2​−1​⋯ps​ps​−1​

通俗来讲， n n n的欧拉函数值就是 n n n对每个质因数分解所得到的质因数进行操作后的连乘积 然后再乘一个 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 n n 是质数，则 φ ( n ) = n − 1 \varphi(n)=n-1 φ(n)=n−1
在线性筛中，一个合数一定是被他的最小质因子筛掉的。假设这个最小质因数是 p j p_j pj​，因此一定存在一个 m = p j ⋅ i m=p_j \cdot i m=pj​⋅i
此时会出现两种情况：

如果 i i i 能够被 p j p_j pj​ 整除，则 i i i 一定包含了 p j p_j pj​ 的所有质因子，因此我们可以得到：
φ ( m ) = m ⋅ ∏ k = 1 s p k a k = p j ⋅ i ⋅ ∏ k = 1 s p k a k = p j ⋅ φ ( i ) \varphi(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 \varphi(i) φ(m)=m⋅∏k=1s​pkak​​=pj​⋅i⋅∏k=1s​pkak​​=pj​⋅φ(i)

如果 i i i 不能被 p j p_j pj​ 整除，则 i i i 与 p j p_j pj​ 一定是互为质数的，因此有以下式子：
φ ( m ) = φ ( p j ) ⋅ φ ( i ) = φ ( i ) ⋅ ( p j − 1 ) \varphi(m)=\varphi(p_j) \cdot \varphi(i) = \varphi(i) \cdot (p_j-1) φ(m)=φ(pj​)⋅φ(i)=φ(i)⋅(pj​−1)

并且通过这种线性筛，我们可以得到 [ 1 , n ] [1,n] [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);}}}}