欧拉函数

「观前提醒」

「文章仅供学习和参考，如有问题请在评论区提出」

目录

• 定义
• 性质
• 计算公式推导
• 求欧拉函数
  • 分解质因子法
  • 筛法求欧拉函数
• 参考资料

---

定义#

---

欧拉函数的符号表示是 $\phi (n)$ ，表示 $1\sim n$ 中和 $n$ 互质的数的个数。

例如，$\phi (12)=4$，即 $1,5,7,11$ 。

性质#

---

1. 若 $n$ 是质数， 则 $\phi (n)=n-1$。

   质数会和小于它本身的所有正整数互质，即 $n$ 与 $1\sim n-1$ 中所有数互质。

2. 当 $n$ 是奇数时，$\phi (2n)=\phi (n)$。

   只有这一种情况成立，并不是 $n$ 的偶数倍的意思。

3. 如果 $n=p^k$，其中 $p$ 是质数，那么

   $$\begin{array}{}\text{(1)}& \phi (n)& =p^k-p^{k-1}\text{(2)}& & =p^{k-1}(p-1)\text{(3)}& & =p^k(1-\frac{1}{p})\end{array}$$

   $1\sim n$ 中只有不包含质数 $p$，才会与 $n$ 互质。而包含质数 $p$ 的数为 $p$ 倍数，即 $1p,2p,3p,4p,...,p^{k-1}p$ ，总共有 $p^{k-1}$ 个。

   所以去掉包含 $p$ 的数，就是和 $n$ 互质的数的个数，即 $\phi (n)=p^k-p^{k-1}$ 。

   公式变形，就会有上述三个表示方式。

4. 积性函数：若 $gcd(a,b)=1$，则 $\phi (ab)=\phi (a)\phi (b)$ 。

计算公式推导#

---

由唯一分解定理，

$$n=\prod _{i=1}^k{p}_i^{a_i}=p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}...\cdot p_k^{a_k}$$

$p_i$ 是 $n$ 的质因子

提醒：$\prod _a^b$ 是乘积运算符号，代表 $a\sim b$ 所有数的乘积，即 $a\times (a+1)\times ...\times b$ 。

那么有，

$$\phi (n)=\phi (\prod _{i=1}^k{p}_i^{a_i})$$

因为对于任意的 $p_i^{a_i}，p_j^{a_j}(1\le i,j\le k)$ 都是互质的，所以用到上面的性质4：若 $gcd(a,b)=1$，则 $\phi (ab)=\phi (a)\phi (b)$ 。那么可以推出，

$$\begin{array}{}\text{(4)}& \phi (n)& =\phi (\prod _{i=1}^k{p}_i^{a_i})\text{(5)}& & =\prod _{i=1}^k\phi (p_i^{a_i})\end{array}$$

然后再根据性质3，推出

$$\begin{array}{}\text{(6)}& \phi (n)& =\phi (\prod _{i=1}^k{p}_i^{a_i})\text{(7)}& & =\prod _{i=1}^k\phi (p_i^{a_i})\text{(8)}& & =\prod _{i=1}^k{p}_i^{a_i-1}(p_i-1)\text{(9)}& & =\prod _{i=1}^k{p}_i^{a_i}(1-\frac{1}{p_i}))\end{array}$$

最后进行公式变形，可得

$$\begin{array}{}\text{(10)}& \phi (n)& =\phi (\prod _{i=1}^k{p}_i^{a_i})\text{(11)}& & =\prod _{i=1}^k\phi (p_i^{a_i})\text{(12)}& & =\prod _{i=1}^k{p}_i^{a_i-1}(p_i-1)\text{(13)}& & =\prod _{i=1}^k{p}_i^{a_i}(1-\frac{1}{p_i})\text{(14)}& & =\prod _{i=1}^k{p}_i^{a_i}\times \prod _{i=1}^k(1-\frac{1}{p_i})\text{(15)}& & =n\times \prod _{i=1}^k\frac{p_i-1}{p_i}\text{(16)}& & =n\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times ...\times \frac{p_k-1}{p_k}\end{array}$$

公式进行整理，可得

$$\begin{array}{}\text{(17)}& \phi (n)& =n\times \prod _{i=1}^k\frac{p_i-1}{p_i}\text{(18)}& & =n\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times ...\times \frac{p_k-1}{p_k}\end{array}$$

观察公式就能发现，欧拉函数仅与 $n$ 及其质因子有关。

求欧拉函数#

---

分解质因子法#

---

思路：用试除法分解出 $n$ 的所有质因子，然后根据推导的公式求解一个数的欧拉函数。

时间复杂度：$O(\sqrt{n})$

代码：

// 分解质因数求欧拉函数
int phi(int n) {
    int res = n;
    // 分解质因子
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            // 公式求值
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / i * (i - 1);
    
    return res;
}

筛法求欧拉函数#

---

// 线性筛法求 1 ~ n 的 质数

const int N = 1e5 + 10;
int p[N], cnt;	// p[]存储所有素数
bool st[N];	 // st[x]存储x是否被筛掉

void get_primes(int n) {
	st[1] = true;
    
    for (int i = 2; i <= n; i++) {
        if (!st[i]) p[cnt++] = i;
        for (int j = 1; p[j] <= n / i; j++) {
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
}

思路：

观察上面的线性筛质数的代码，我们可以再用一个 phi[] 来存储每一个数的欧拉函数，即 $phi[i]=\phi (i)$ 。

若 $i$ 是质数，根据性质1可得 $phi[i]=i-1$ 。

而且在线性筛中，每个合数（非质数）都会被自身的最小质因子筛掉。那么设 $p_j$ 是 $m$ 的最小质因子，根据线性筛，就想办法让 $m$ 通过 $m=p_j\times i$ 筛掉。

• 若 $i$ 能被 $p_j$ 整除，则 $i$ 就包含了 $m$ 的所有质因子。

  若 $i$ 能被 $p_j$ 整除，说明 $p_j$ 也是 $i$ 的质因子。又因为 $p_j$ 也是 $m$ 的质因子，而且 $m=p_j\times i$ ，所以 $i$ 就包含了 $m$ 的所有质因子。

  然后再根据推导的公式变形，得

  $$\begin{array}{}\text{(19)}& \phi (m)& =m\times \prod _{k=1}^S\frac{p_k-1}{p_k}\text{(20)}& & =p_j\times i\times \prod _{k=1}^S\frac{p_k-1}{p_k}\text{(21)}& & =p_j\times \phi (i)\end{array}$$

  根据推导公式，一个数得欧拉函数只与其本身和其质因子有关。

  虽然 $\prod _{k=1}^S\frac{p_k-1}{p_k}$ 是从 $\phi (m)$ 推导出来的，但是因为 $i$ 与 $m$ 的质因子相同，所以也可以被用来推导出 $\phi (i)$ 。

• 若 $i$ 不能被 $p_j$ 整除，则 $i$ 和 $p_j$ 是互质的。

  因为 $p_j$ 是质数，除了 $p_j$ 本身，就没有其他的质因子。若 $i$ 不能被 $p_j$ 整除，那么 $i$ 和 $p_j$ 就没有相同的质因子，那么两者就是互质的。

  然后根据性质4和性质1进行公式变形，得

  $$\begin{array}{}\text{(22)}& \phi (m)& =\phi (p_j\times i)\text{(23)}& & =\phi (p_j)\times \phi (i)\text{(24)}& & =(p_j-1)\times \phi (i)\end{array}$$

总结上面的思路，就能得到所有的情况，

• 若 $i$ 是 质数，得 $\phi (i)=i-1$ 。
• 若 $i$ 不是质数，说明已经被自己的质因子赋值了。
• 遍历 $p[1\sim cnt]$ ，
  • 若 $i$ 能被 $p_j$ 整除，得 $\phi (m)=p_j\times \phi (i)$ ，并退出遍历。
  • 若 $i$ 不能被 $p_j$ 整除，得 $\phi (m)=(p_j-1)\times \phi (i)$ 。

时间复杂度： $O(N)$

代码：

const int N = 1e5 + 10;
int p[N], cnt;	// p[] 存储所有素数
int phi[N];	// phi[x] 存储 x 的欧拉函数值
bool st[N];	// st[x] 存储 x 是否被筛掉

// 线性筛法求欧拉函数
void get_phi(int n) {
    phi[1] = 1;
    st[1] = true;
    
    for (int i = 2; i <= n; i++) {
        // 没有被筛过，说明是质数
        if (!st[i]) {
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        
        for (int j = 0; p[j] <= n / i; j++) {
            int m = i * p[j];
          	st[m] = true;
            // 判断是否能整除，然后根据公式赋值
            if (i % p[j] == 0) {
                phi[m] = p[j] * phi[i];
                break;
            } else phi[m] = (p[j] - 1) * phi[i];
        }
    }
}

---

参考资料#

---

欧拉函数 - OI Wiki (oi-wiki.org)：https://oi-wiki.org/math/number-theory/euler/

【RSA原理2】浅谈--什么是欧拉函数 韦_恩的博客-CSDN博客：https://blog.csdn.net/qq_42539194/article/details/118514310

董晓算法 515 筛法求欧拉函数：https://www.bilibili.com/video/BV1VP411p7Bs

---