「观前提醒」
「文章仅供学习和参考，如有问题请在评论区提出」
欧拉函数
定义
欧拉函数的符号表示是 (varphi (n)) ，表示 (1sim 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)) 。
计算公式推导
由唯一分解定理，
(p_{i}) 是 (n) 的质因子
提醒：$prod_{a}^{b} $ 是乘积运算符号，代表 (a sim b) 所有数的乘积，即 (a times (a + 1) times ... times b) 。
那么有，
因为对于任意的 (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)) 。那么可以推出，
然后再根据性质3，推出
最后进行公式变形，可得
公式进行整理，可得
观察公式就能发现，欧拉函数仅与 (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
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
