欧拉函数（Euler’s Totient Function）

欧拉函数是数论中的核心概念之一，广泛应用于密码学、模运算和群论等领域。它是指一个正整数 $n$ 与 $1, 2, \dots, n-1$ 互质的数的个数。

1. 什么是欧拉函数？

对于正整数 $n$，欧拉函数 $\varphi(n)$ 定义为：

小于或等于 $n$ 且与 $n$ 互素（即 $\gcd(k, n) = 1$）的正整数 $k$ 的个数。

用集合表示为： $\varphi(n) = \left| \{ k \in \mathbb{Z}^+ \mid 1 \leq k \leq n,\ \gcd(k, n) = 1 \} \right|$

2. 简单例子

$n$	与 $n$ 互素的数	$\varphi(n)$
1	{1}	1
2	{1}	1
3	{1, 2}	2
4	{1, 3}	2
5	{1, 2, 3, 4}	4
6	{1, 5}	2
9	{1, 2, 4, 5, 7, 8}	6
12	{1, 5, 7, 11}	4

3. 核心性质

3.1 质数的情况

若 $p$ 是质数，则： $\varphi(p) = p - 1$

因为 $1, 2, \dots, p-1$ 都与 $p$ 互质。

3.2 质数幂的情况

若 $p$ 是质数，$k \geq 1$，则： $\varphi(p^k) = p^k - p^{k-1} = p^k \left(1 - \frac{1}{p}\right)$

3.3 积性函数

若 $\gcd(m, n) = 1$，则： $\varphi(mn) = \varphi(m) \cdot \varphi(n)$

注意：仅当 $m$ 与 $n$ 互质时成立。

3.4 通用公式（基于质因数分解）

设 $n$ 的质因数分解为： $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$ 则： $\varphi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right)$

✅ 示例：计算 $\varphi(60)$

质因数分解：$60 = 2^2 \cdot 3 \cdot 5$
应用公式： $\varphi(60) = 60 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) = 60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16$

4. 重要应用

4.1 欧拉定理（Euler’s Theorem）

若 $\gcd(a, n) = 1$，则： $a^{\varphi(n)} \equiv 1 \pmod{n}$

特例：当 $n = p$（质数）时，退化为费马小定理：$a^{p-1} \equiv 1 \pmod{p}$

4.2 RSA 加密算法

RSA 的安全性依赖于大整数分解困难性，其密钥生成过程中需计算： $\varphi(n) = \varphi(pq) = (p-1)(q-1)$ 其中 $p, q$ 为大质数。

4.3 模 $n$ 乘法群的阶

模 $n$ 下所有与 $n$ 互质的剩余类构成一个乘法群，其阶（元素个数）正好是 $\varphi(n)$。

5. 快速计算技巧

方法一：直接枚举（适用于小 $n$）

int phi(int n) {
    if (n <= 0) return 0;
    int count = 0;
    for (int k = 1; k <= n; ++k) {
        if (__gcd(k, n) == 1) {
            count++;
        }
    }
    return count;
}

方法二：利用质因数分解实现欧拉函数（高效）

int phi_fast(int n) {
    if (n <= 1) return (n == 1) ? 1 : 0;
    
    int result = n;
    
    // 处理因子 2
    if (n % 2 == 0) {
        result -= result / 2;  // 等价于 result *= (1 - 1/2)
        while (n % 2 == 0) {
            n /= 2;
        }
    }
    
    // 处理奇数因子
    for (int p = 3; p * p <= n; p += 2) {
        if (n % p == 0) {
            result -= result / p;  // 等价于 result *= (1 - 1/p)
            while (n % p == 0) {
                n /= p;
            }
        }
    }
    
    // 如果剩下的是一个大质数
    if (n > 1) {
        result -= result / n;
    }
    
    return result;
}

或者可以拆为两个步骤：
获得一个整数的所有质数因子 + 计算欧拉函数

获得一个整数的所有质数因子$O(\sqrt{n})$

// 返回 n 的所有质因子及其指数，按升序排列
vector<pair<long long,int>> factorize(long long n) {
    // 每个pair是(质因子, 指数)
    vector<pair<long long,int>> res;
    auto push = [&](long long p) {
        int cnt = 0;
        while (n % p == 0) { n /= p; ++cnt; }
        if (cnt) res.emplace_back(p, cnt);
    };
    // 2 单独处理，方便后面步长 2
    push(2);
    // 试除奇数到 sqrt(n) 优化，只考虑奇数因子
    for (long long p = 3; p * p <= n; p += 2) push(p);
    // 如果还剩一个 >1 的质数
    if (n > 1) res.emplace_back(n, 1);
    return res;
}

计算欧拉函数 $O(\sqrt n)$

// 计算欧拉函数 φ(n)
int euler_phi(int n) {
    if (n == 1) return 1;  // φ(1) = 1
    if (n <= 0) return 0;  // 通常不考虑非正整数
    
    vector<pair<int, int>> factors = factorize(n);
    int result = n;
    
    for (auto &factor : factors) {
        int p = factor.first;
        result = result / p * (p - 1);  // 整数运算，无浮点
    }
    
    return result;
}

6. 小结

概念	说明
定义	$\varphi(n)$ = 与 $n$ 互质且 $\leq n$ 的正整数个数
关键公式	$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$
核心性质	积性函数、质数幂公式
重要定理	欧拉定理：$a^{\varphi(n)} \equiv 1 \pmod{n}$（当 $\gcd(a,n)=1$）
应用场景	RSA 加密、数论、群论、模运算

💡 提示：掌握欧拉函数的关键在于理解其与质因数的关系，并熟练运用积性性质简化计算。

欧拉函数