「观前提醒」
「文章仅供学习和参考，如有问题请在评论区提出」
欧拉函数
定义
欧拉函数的符号表示是 \(\varphi (n)\) ，表示 \(1\sim n\) 中和 \(n\) 互质的数的个数。
例如，\(\varphi (12) = 4\)，即 \(1,5,7,11\) 。
性质
-
若 \(n\) 是质数， 则 \(\varphi (n) = n - 1\)。
质数会和小于它本身的所有正整数互质，即 \(n\) 与 \(1 \sim n - 1\) 中所有数互质。
-
当 \(n\) 是奇数时，\(\varphi(2n) = \varphi(n)\)。
只有这一种情况成立，并不是 \(n\) 的偶数倍的意思。
-
如果 \(n = p^{k}\)，其中 \(p\) 是质数，那么
\[\begin{align} \varphi(n) & = p^{k} - p^{k - 1} \\ & = p^{k - 1}(p - 1) \\ & = p^{k}(1 - \frac{1}{p} ) \end{align} \]\(1 \sim n\) 中只有不包含质数 \(p\)，才会与 \(n\) 互质。而包含质数 \(p\) 的数为 \(p\) 倍数，即 \(1p,2p,3p,4p,...,p^{k - 1}p\) ，总共有 \(p^{k - 1}\) 个。
所以去掉包含 \(p\) 的数，就是和 \(n\) 互质的数的个数，即 \(\varphi(n) = p^{k} - p^{k - 1}\) 。
公式变形，就会有上述三个表示方式。
-
积性函数：若 \(\gcd(a,b) = 1\)，则 \(\varphi(ab) = \varphi(a)\varphi(b)\) 。
计算公式推导
由唯一分解定理，
\[n = {\textstyle \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\) 。
那么有，
\[\varphi(n) = \varphi({\textstyle \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\)，则 \(\varphi(ab) = \varphi(a)\varphi(b)\) 。那么可以推出，
\[\begin{align} \varphi(n) & = \varphi({\textstyle \prod_{i = 1}^{k}}p_{i}^{a_{i}})\\ & = {\textstyle \prod_{i = 1}^{k}} \varphi(p_{i}^{a_{i}}) \end{align} \]然后再根据性质3，推出
\[\begin{align} \varphi(n) & = \varphi({\textstyle \prod_{i = 1}^{k}}p_{i}^{a_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} \varphi(p_{i}^{a_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i} - 1}(p_{i} - 1)\\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i}}(1 - \frac{1}{p_{i}}))\\ \end{align} \]最后进行公式变形，可得
\[\begin{align} \varphi(n) & = \varphi({\textstyle \prod_{i = 1}^{k}}p_{i}^{a_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} \varphi(p_{i}^{a_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i} - 1}(p_{i} - 1) \\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i}}(1 - \frac{1}{p_{i}}) \\ & = {\textstyle \prod_{i = 1}^{k}} p_{i}^{a_{i}} \times {\textstyle \prod_{i = 1}^{k}}(1 - \frac{1}{p_{i}}) \\ & = n \times {\textstyle \prod_{i = 1}^{k}} \frac{p_{i} - 1}{p_{i}} \\ & = n \times \frac{p_{1} - 1}{p_{1}} \times \frac{p_{2} - 1}{p_{2}} \times ... \times \frac{p_{k} - 1}{p_{k}} \end{align} \]公式进行整理，可得
\[\begin{align} \varphi(n) & = n \times {\textstyle \prod_{i = 1}^{k}} \frac{p_{i} - 1}{p_{i}} \\ & = n \times \frac{p_{1} - 1}{p_{1}} \times \frac{p_{2} - 1}{p_{2}} \times ... \times \frac{p_{k} - 1}{p_{k}} \end{align} \]观察公式就能发现，欧拉函数仅与 \(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] = \varphi(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{align} \varphi(m) & = m \times {\textstyle \prod_{k = 1}^{S}} \frac{p_{k} - 1}{p_{k}} \\ & = p_{j} \times i \times {\textstyle \prod_{k = 1}^{S}} \frac{p_{k} - 1}{p_{k}} \\ & = p_{j} \times \varphi(i) \end{align} \]根据推导公式，一个数得欧拉函数只与其本身和其质因子有关。
虽然 \({\textstyle \prod_{k = 1}^{S}} \frac{p_{k} - 1}{p_{k}}\) 是从 \(\varphi(m)\) 推导出来的，但是因为 \(i\) 与 \(m\) 的质因子相同，所以也可以被用来推导出 \(\varphi(i)\) 。
-
若 \(i\) 不能被 \(p_{j}\) 整除，则 \(i\) 和 \(p_{j}\) 是互质的。
因为 \(p_{j}\) 是质数，除了 \(p_{j}\) 本身，就没有其他的质因子。若 \(i\) 不能被 \(p_{j}\) 整除，那么 \(i\) 和 \(p_{j}\) 就没有相同的质因子，那么两者就是互质的。
然后根据性质4和性质1进行公式变形，得
\[\begin{align} \varphi(m) & = \varphi(p_{j} \times i) \\ & = \varphi(p_{j}) \times \varphi(i) \\ & = (p_{j} - 1) \times \varphi(i) \end{align} \]
总结上面的思路，就能得到所有的情况，
- 若 \(i\) 是 质数，得 \(\varphi(i) = i - 1\) 。
- 若 \(i\) 不是质数，说明已经被自己的质因子赋值了。
- 遍历 \(p[1 \sim cnt]\) ，
- 若 \(i\) 能被 \(p_{j}\) 整除，得 \(\varphi(m) = p_{j} \times \varphi(i)\) ，并退出遍历。
- 若 \(i\) 不能被 \(p_{j}\) 整除，得 \(\varphi(m) = (p_{j} - 1) \times \varphi(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
标签：textstyle,frac,函数,align,varphi,times,prod,欧拉 From： https://www.cnblogs.com/oneway10101/p/17565867.html