欧拉函数-五八三

「观前提醒」

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

欧拉函数#

定义#

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

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

性质#

若 $n$ 是质数，则 $φ (n) = n - 1$ 。

质数会和小于它本身的所有正整数互质，即 $n$ 与 $1 \sim n - 1$ 中所有数互质。
当 $n$ 是奇数时， $φ (2 n) = φ (n)$ 。

只有这一种情况成立，并不是 $n$ 的偶数倍的意思。
如果 $n = p^{k}$ ，其中 $p$ 是质数，那么

$\begin{aligned} (1) & φ (n) & = p^{k} - p^{k - 1} \\ (2) & = p^{k - 1} (p - 1) \\ (3) & = p^{k} (1 - \frac{1}{p}) \end{aligned}$

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

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

公式变形，就会有上述三个表示方式。
积性函数：若 $gcd (a, b) = 1$ ，则 $φ (a b) = φ (a) φ (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$ 。

那么有，

φ (n) = φ (\prod_{i = 1}^{k} p_{i}^{a_{i}})

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

\begin{aligned} (4) & φ (n) & = φ (\prod_{i = 1}^{k} p_{i}^{a_{i}}) \\ (5) & = \prod_{i = 1}^{k} φ (p_{i}^{a_{i}}) \end{aligned}

然后再根据性质3，推出

\begin{aligned} (6) & φ (n) & = φ (\prod_{i = 1}^{k} p_{i}^{a_{i}}) \\ (7) & = \prod_{i = 1}^{k} φ (p_{i}^{a_{i}}) \\ (8) & = \prod_{i = 1}^{k} p_{i}^{a_{i} - 1} (p_{i} - 1) \\ (9) & = \prod_{i = 1}^{k} p_{i}^{a_{i}} (1 - \frac{1}{p_{i}})) \end{aligned}

最后进行公式变形，可得

\begin{aligned} (10) & φ (n) & = φ (\prod_{i = 1}^{k} p_{i}^{a_{i}}) \\ (11) & = \prod_{i = 1}^{k} φ (p_{i}^{a_{i}}) \\ (12) & = \prod_{i = 1}^{k} p_{i}^{a_{i} - 1} (p_{i} - 1) \\ (13) & = \prod_{i = 1}^{k} p_{i}^{a_{i}} (1 - \frac{1}{p_{i}}) \\ (14) & = \prod_{i = 1}^{k} p_{i}^{a_{i}} \times \prod_{i = 1}^{k} (1 - \frac{1}{p_{i}}) \\ (15) & = n \times \prod_{i = 1}^{k} \frac{p_{i} - 1}{p_{i}} \\ (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{aligned}

公式进行整理，可得

\begin{aligned} (17) & φ (n) & = n \times \prod_{i = 1}^{k} \frac{p_{i} - 1}{p_{i}} \\ (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{aligned}

观察公式就能发现，欧拉函数仅与 $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[] 来存储每一个数的欧拉函数，即 $p h i [i] = φ (i)$ 。

若 $i$ 是质数，根据性质1可得 $p h i [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{aligned} (19) & φ (m) & = m \times \prod_{k = 1}^{S} \frac{p_{k} - 1}{p_{k}} \\ (20) & = p_{j} \times i \times \prod_{k = 1}^{S} \frac{p_{k} - 1}{p_{k}} \\ (21) & = p_{j} \times φ (i) \end{aligned}$

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

虽然 $\prod_{k = 1}^{S} \frac{p_{k} - 1}{p_{k}}$ 是从 $φ (m)$ 推导出来的，但是因为 $i$ 与 $m$ 的质因子相同，所以也可以被用来推导出 $φ (i)$ 。
若 $i$ 不能被 $p_{j}$ 整除，则 $i$ 和 $p_{j}$ 是互质的。

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

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

$\begin{aligned} (22) & φ (m) & = φ (p_{j} \times i) \\ (23) & = φ (p_{j}) \times φ (i) \\ (24) & = (p_{j} - 1) \times φ (i) \end{aligned}$

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

若 $i$ 是质数，得 $φ (i) = i - 1$ 。
若 $i$ 不是质数，说明已经被自己的质因子赋值了。
遍历 $p [1 \sim c n t]$ ，
- 若 $i$ 能被 $p_{j}$ 整除，得 $φ (m) = p_{j} \times φ (i)$ ，并退出遍历。
- 若 $i$ 不能被 $p_{j}$ 整除，得 $φ (m) = (p_{j} - 1) \times φ (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

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END

博客文章