数论 -- 欧拉函数求解详解（含推导及证明）

文章目录

• 欧拉函数求解
• • 公式法 -- O(√n)
  • • 基本概念及公式推导
    • 代码模板
  • 欧拉筛法 -- O(n)
  • • 基本概念及公式推导
    • 代码模板

欧拉函数求解

公式法 – O(√n)

基本概念及公式推导

$欧拉函数$

设 Φ（n） 表示 集合{ 0 ， 1， ···，n - 1 }中与 n 互素的数的个数

对于给定的正整数 n , 素因子分解式为
n = p 1 α 1 ∗ p 2 α 2 ∗ ⋅ ⋅ ⋅ ∗ p k α k n = p_1^{α_1}*p_2^{α_2}*···*p_k^{α_k} n=p1α1​​∗p2α2​​∗⋅⋅⋅∗pkαk​​

令 A i A_i Ai​ ={ x | x 小于正整数 n 的 集合{ 0 ，1 ，···，n - 1 }，且 p i p_i pi​ 整除 x }

$容斥原理$

定义 ：在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，可以先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复设 S 是有穷集， p 1 ， p 2 ， ⋅ ⋅ ⋅ ， p n p_1，p_2，···，p_n p1​，p2​，⋅⋅⋅，pn​ 是 n 个性质

• S 中 的任何元素 x 要么具有性质 p i p_i pi​，要么不具有性质 p i p_i pi​，两种情况必居其一

令 A i A_i Ai​表示 S 中具有 性质 p i p_i pi​ 的元素构成的子集

则 S 中不具有性质 p 1 ， p 2 ， ⋅ ⋅ ⋅ ， p n p_1，p_2，···，p_n p1​，p2​，⋅⋅⋅，pn​ 的 元素数为
∣ A ˉ 1 ∩ A ˉ 2 ∩ ⋅ ⋅ ⋅ ∩ A ˉ n ∣ = ∣ S ∣ − ∑ i = 1 n ∣ A i ∣ + ∑ 1 ≤ i < j ≤ n ∣ A i ∩ A j ∣ − ∑ 1 ≤ i < j < k ≤ n ∣ A i ∩ A j ∩ A k ∣ + ⋅ ⋅ ⋅ + ( − 1 ) n ∣ A i ∩ A j ∩ ⋅ ⋅ ⋅ ∩ A n ∣ |\bar{A}_1\cap \bar{A}_2\cap···\cap\bar{A}_n| = |S| - \sum^n_{i=1}|A_i| + \sum_{1≤i∣Aˉ1​∩Aˉ2​∩⋅⋅⋅∩Aˉn​∣=∣S∣−i=1∑n​∣Ai​∣+1≤i<j≤n∑​∣Ai​∩Aj​∣−1≤i<j<k≤n∑​∣Ai​∩Aj​∩Ak​∣+⋅⋅⋅+(−1)n∣Ai​∩Aj​∩⋅⋅⋅∩An​∣
| 集合 | 表示集合中元素的个数

那么
Φ ( n ) = ∣ A ˉ 1 ∩ A ˉ 2 ∩ ⋅ ⋅ ⋅ ∩ A ˉ k ∣ Φ ( n ) =|\bar{A}_1\cap \bar{A}_2\cap···\cap\bar{A}_k| Φ(n)=∣Aˉ1​∩Aˉ2​∩⋅⋅⋅∩Aˉk​∣
下面计算等式右边的各项
∣ A i ∣ = n p i , i = 1 ， 2 ， ⋅ ⋅ ⋅ ， k |A_i|=\frac{n}p_i , i = 1，2，···，k ∣Ai​∣=pn​i​,i=1，2，⋅⋅⋅，k

∣ A i ∩ A j ∣ = n p i p j ， 1 ≤ i < j ≤ n |A_i\cap A_j| = \frac{n}{p_ip_j}， 1 ≤i∣Ai​∩Aj​∣=pi​pj​n​，1≤i<j≤n

$$\cdot \cdot \cdot$$

根据容斥原理有
Φ ( n ) = ∣ A ˉ 1 ∩ A ˉ 2 ∩ ⋅ ⋅ ⋅ ∩ A ˉ n ∣ Φ(n) =|\bar{A}_1\cap \bar{A}_2\cap···\cap\bar{A}_n| Φ(n)=∣Aˉ1​∩Aˉ2​∩⋅⋅⋅∩Aˉn​∣

= n − ( n p 1 + n p 2 + ⋅ ⋅ ⋅ n p k ) + ( n p 1 p 2 + n p 1 p 3 + ⋅ ⋅ ⋅ n p k − 1 p k ) − ⋅ ⋅ ⋅ + ( − 1 ) k n p 1 p 2 ⋅ ⋅ ⋅ p k =n -(\frac{n}p_1+\frac{n}p_2+···\frac{n}p_k) + (\frac{n}{p_1p_2}+\frac{n}{p_1p_3}+···\frac{n}{p_{k-1}p_k})-···+(-1)^k\frac{n}{p_1p_2···p_k} =n−(pn​1​+pn​2​+⋅⋅⋅pn​k​)+(p1​p2​n​+p1​p3​n​+⋅⋅⋅pk−1​pk​n​)−⋅⋅⋅+(−1)kp1​p2​⋅⋅⋅pk​n​

= n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) ⋅ ⋅ ⋅ ( 1 − 1 p k ) ， ( 集合 { 0 ， 1 ， ⋅ ⋅ ⋅ ， n − 1 } 中与 n 互素的数的个数 ) =\color{Orange}n(1- \frac{1}p_1)(1- \frac{1}p_2)···(1- \frac{1}p_k) ，(集合 \{ 0 ， 1， ···，n - 1 \}中与 n 互素的数的个数) =n(1−p1​1​)(1−p1​2​)⋅⋅⋅(1−p1​k​)，(集合{0，1，⋅⋅⋅，n−1}中与n互素的数的个数)

代码模板

int phi(int x)
{int res = x;for(int i = 1; i <= x/i; i ++ )if(x % i == 0){res = res/i*(i-1)// 此为 n × （1 - p 分之一）...while(x % i == 0) x /= i;}if(x > 1) res = res/x*(x - 1);return res;
}

$注意$

此方法适用于求解单个元素时

欧拉筛法 – O(n)

基本概念及公式推导

若不了解欧拉筛的可以点开链接快速学习 数论 – 质数判定及其筛法求解

当求某些 1 ~ n 中每一个数的欧拉函数时，若用公式法，那么时间复杂度 为O(n√n)，太慢，故此我们需要批量预处理计算欧拉函数，这样就可以直接以 O(1) 查询 欧拉函数了

原理

利用欧拉筛，分为 2 种情况

• $i$ 是质数
  • 1 ~ $i-1$ 均与 $i$ 互质，即 $\Phi (i)=i-1$
• $i$ 不是质数
  1. $i\%p[j]==0$ ( $i中包含p[j]$)
     • 此时 $pj$ 一定是 $i$ 的最小质因子，$\Phi (i)$中包含了 ( 1 − 1 p [ j ] 1 ~-~\frac{1}{p[j]} 1 − p[j]1​)
     • 有 $\Phi (i\ast pj)=pj\ast \Phi (i)$
  2. $i\%p[j]!=0$ ( $i中不包含p[j]$)
  • 此时 $i$ 的质因子不包括 $p[j]$
  • 有 Φ ( i ∗ p [ j ] ) = Φ ( i ) ∗ p [ j ] = Φ ( i ) ∗ ( 1 − 1 p [ j ] ) = Φ ( i ) ∗ ( p [ j ] − 1 ) \color{Orange}Φ( ~i~ *~ p[j]) ~=~ Φ(i) ~*~p[j]=Φ(i)~*~(1-\frac{1}{p[j]})~=~Φ(i) ~*~ (p[j] - 1) Φ( i ∗ p[j]) = Φ(i) ∗ p[j]=Φ(i) ∗ (1−p[j]1​) = Φ(i) ∗ (p[j]−1)

$性质$

• 1 不是质数，也不是合数，它和所有的正整数互质。1 和 1互质这个命题，也是正确的！
• 一个质数 n 与比它小的每一个非0的自然数都互质，故与 质数 n 互质的个数为 n - 1

代码模板

int primes[N]; // primes[] 存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x] 存储 x 是否被筛掉void get_eulers(int n)
{euler[1] = 1; //1 和 1互质这个命题，也是正确的！故 与 1 互质的个数 为 1for(int i = 2; i <= n; i ++ ){if(!st[i]){primes[cnt++] = i;euler[i] = i - 1; // 与 质数 i 互质的个数为 i - 1}for(int j = 0; primes[j] <= n/i; j ++ ){int t = primes[j] * i;st[t] = true;if(i % primes[j] == 0){euler[t] = euler[i] * primes[j];break;}euler[t] = euler[i] * (primes[j] - 1);// i % pj != 0}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！