# Road Map
欧拉函数是一个重要的数论函数,它与素数分解和模运算有关。欧拉函数通常用 φ(n) 表示,它表示小于等于 n 的正整数中与 n 互质的数的个数。
# 欧拉函数的应用
以下是欧拉函数的一些应用:
- 判断两个数是否互质:如果两个数 a 和 b 互质,那么 φ(a) × φ(b) = φ(a × b)。
- 求解同余方程:对于同余方程 a^x ≡ b (mod n),如果 n 是质数,那么有 a^φ(n) ≡ 1 (mod n)。因此,如果 gcd(x, φ(n)) = 1,那么 x 的解就是 x ≡ a^(-1) × b (mod n)。
- RSA 加密算法:RSA 是一种公钥加密算法,它的安全性基于大素数分解的困难性。在 RSA 算法中,欧拉函数的值起着重要作用,它用于计算加密和解密密钥。
- 原根:欧拉函数 φ(n) 是 n 的原根的个数。原根是一个数,它的幂可以取遍 n 的所有与 n 互质的余数。
- 分解质因数:欧拉函数可以用来分解质因数。如果知道一个数 n 的欧拉函数的值,那么可以计算出 n 的所有质因数和它们的指数。
# 欧拉函数
定义:
中与 N 互质的数的个数被称为 欧拉函数,记为
根据算数基本定理,任何一个正整数 ,则 :
# 证明
容斥原理
1、从 1~N 中去掉 的所有倍数
2、加上所有 两个数的
$N- \frac{N} {p_1}- \frac{N} {p_2} - ...- \frac{N} {p_k} + \frac{N}{p_1p_2} + \frac{N}{p_2p_3} + \frac{N}{p_1p_3} + ... $
3、减去 所有三个数的倍数
也就是容斥原理
等价于
# 代码实现
求数字 的欧拉函数
LL res = a;
for (int i = 2; i <= a / i; i ++ ) {
if (a % i == 0) {
res = res * (i-1) / i;
while (a %i == 0) a/= i;
}
}
if (a > 1) res = res * (a-1) / a;
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8