CC++ & Algorithm

欧拉函数的性质与计算公式

极难2
语言版本：通用
概述：利用欧拉函数的乘积性和质数幂公式，我们可以直接通过分解质因数来快速计算任意正整数的欧拉函数值。

欧拉函数：快速计算与n互质的数的个数

你有没有遇到过这样的问题：老师让你把全班30个同学平均分成若干组，每组人数要和30互质（即最大公约数为1），这样每组人数有哪些可能？其实就是求1到30中与30互质的数，也就是30的欧拉函数值 φ(30)。用手算很麻烦，但如果你知道欧拉函数的公式，几秒钟就能算出来。欧拉函数是数论的核心工具，在密码学（比如RSA加密）中也扮演重要角色。今天我们就来学会如何快速计算任意正整数的欧拉函数。

什么是欧拉函数？

欧拉函数 φ(n) 表示从1到n（包括1和n）中，与n互质的数的个数。两个数互质就是它们的最大公约数为1。比如 φ(6)=2，因为1到6中与6互质的只有1和5（6和2、3、4都不互质）。上一讲我们是用挨个检查的方法，但n很大时（比如10^12），循环就太慢了。幸好，欧拉函数有神奇的快速计算公式，只需要知道n的质因数分解。

欧拉函数的三大核心性质

掌握了下面三条性质，你就能自己推导出公式。

性质1：质数的欧拉函数

如果 p 是一个质数，那么 φ(p) = p - 1。

因为质数只能被1和自己整除，所以从1到p-1的所有数都和p互质。比如 p=7，1,2,3,4,5,6都与7互质，共6个。

性质2：质数幂的欧拉函数

如果 p 是质数，k 是正整数，那么 φ(p^k) = p^k - p^{k-1} = p^{k-1} × (p-1)。

为什么？考虑 p^k 的所有因子中，哪些数不互质？只要一个数含有因子 p，它就不与 p^k 互质。从1到 p^k 中，含因子 p 的数有：p, 2p, 3p, …, p^k，一共 p^{k-1} 个（因为 p^k ÷ p = p^{k-1}）。所以互质的个数就是总数减去这些不互质的：p^k - p^{k-1}。

生活例子：假设有 p=3, k=2，即 3^2=9 个糖果。你想把糖果分给小朋友，要求每个小朋友拿到的糖果数和9互质。那么糖果数不能是3的倍数，也就是3,6,9这三种不行。所以可选的糖果数有1,2,4,5,7,8共6种，正好对应 φ(9)=6。

性质3：积性函数——互质时才能相乘

如果 a 和 b 互质（即 gcd(a,b)=1），那么 φ(a×b) = φ(a) × φ(b)。

注意：必须 a 和 b 互质！不互质时公式不成立。比如 a=2, b=4，它们不互质（最大公约数为2），φ(2)=1, φ(4)=2，但 φ(8)=4，1×2=2≠4。而 a=2, b=3 互质，φ(2)=1, φ(3)=2，φ(6)=2，1×2=2 成立。

生活类比：两个互质的数就像两个不同班级的学生，每个班级的“互质人数”可以直接乘起来得到合班后的总互质人数。但如果两个班有重复（不互质），就会算重，不能直接乘。

从性质推导通用公式

任何一个正整数 n 都可以分解为质因数的幂的乘积（算术基本定理）：

n = p1^{k1} × p2^{k2} × … × pr^{kr}

这里 p1, p2, …, pr 是不同的质数。由于这些质因数幂之间互质（因为质数不同），所以可以用积性性质：

φ(n) = φ(p1^{k1}) × φ(p2^{k2}) × … × φ(pr^{kr})
     = (p1^{k1} - p1^{k1-1}) × (p2^{k2} - p2^{k2-1}) × … × (pr^{kr} - pr^{kr-1})

也可以提取公因式写成：

φ(n) = p1^{k1-1}×(p1-1) × p2^{k2-1}×(p2-1) × … × pr^{kr-1}×(pr-1)

更简洁的形式是连乘公式：

φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × … × (1 - 1/pr)

怎么来的？因为 p^k - p^{k-1} = p^k × (1 - 1/p)，而所有 p^k 相乘就是 n，所以 φ(n) = n × ∏_{p|n} (1 - 1/p)。只需要对 n 的每个不同质因数 p，乘以 (1 - 1/p) 即可。

例子：n = 12 = 2² × 3¹，质因数为 2 和 3。 φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4。验证：1,5,7,11 共4个。

n = 30 = 2 × 3 × 5，质因数为 2,3,5。 φ(30) = 30 × (1-1/2) × (1-1/3) × (1-1/5) = 30 × 1/2 × 2/3 × 4/5 = 8。验证：1,7,11,13,17,19,23,29 共8个。

编程实现：用质因数分解快速计算欧拉函数

我们用循环从2到√n试除，找出所有质因数，同时用整数运算更新结果。注意公式中有除法，我们不用浮点数，而是用“先除后乘”来保证精确整数运算。

整数实现原理

设 result = n。对于每个质因数 p：

  1. 如果 n 能被 p 整除，就执行 result = result / p × (p-1)
  2. 然后把 n 中所有的 p 因子除掉（除干净）
  3. 继续找下一个质因数

最后，如果剩下的 n > 1，说明还有一个大于√原n的质因子，也需要处理一次。

为什么可以先除后乘？因为 p 是 n 的因子，而 result 初始为 n，所以 p 一定能整除 result，不会丢失精度。

C++ 代码（带注释）

#include <iostream>
using namespace std;

// 函数：计算欧拉函数 φ(n)
int euler_phi(int n) {
    int result = n;   // 结果初始化为 n
    int temp = n;     // temp 用来分解质因数，不改变原 n
    // 从 2 开始试除，到 sqrt(temp)
    for (int p = 2; p * p <= temp; p++) {
        if (temp % p == 0) {               // 找到质因子 p
            // 根据公式：result = result / p * (p-1)
            result = result / p * (p - 1);
            // 将 temp 中所有因子 p 除掉
            while (temp % p == 0) {
                temp /= p;
            }
        }
    }
    // 如果最后 temp > 1，说明它本身是一个质数（大于 sqrt(原n)）
    if (temp > 1) {
        result = result / temp * (temp - 1);
    }
    return result;
}

int main() {
    int n;
    cout << "请输入一个正整数 n: ";
    cin >> n;
    cout << "φ(" << n << ") = " << euler_phi(n) << endl;
    return 0;
}

Python 代码（带注释）

def euler_phi(n):
    result = n           # 结果初始化为 n
    temp = n             # temp 用来分解质因数
    p = 2
    while p * p <= temp:
        if temp % p == 0:               # 找到质因子 p
            # 根据公式更新 result，注意要用整除 //
            result = result // p * (p - 1)
            # 除掉 temp 中所有 p 因子
            while temp % p == 0:
                temp //= p
        p += 1
    # 如果还有剩余的大质数
    if temp > 1:
        result = result // temp * (temp - 1)
    return result

# 主程序
n = int(input("请输入一个正整数 n: "))
print(f"φ({n}) = {euler_phi(n)}")

新手容易犯的错误

  1. 忘记处理最后的大质因子
    如果 n 本身是质数（比如17），循环从2到4都找不到因子，最后 temp 仍然为17，大于1。必须把这个质数也处理一次。否则 result 会保持17，正确答案应为16。

  2. 用浮点数计算 (1 - 1/p) 导致精度丢失
    比如 n=10，若用 result = n * (1 - 1/2) * (1 - 1/5)，浮点运算可能得到3.99999，取整后变成3（实际是4）。所以一定要用整数运算。

  3. 顺序弄反：先乘后除
    如果用 result = result * (p-1) / p，在C++中可能先乘法导致溢出，而且除法不一定整除（虽然数学上整除，但整数除法会截断）。所以坚持先除后乘。

  4. 忽略互质条件，对不互质的数直接使用积性公式
    比如算 φ(100)，不能直接分解为 φ(10) × φ(10)，因为10和10不互质。必须质因数分解成 2²×5²，再用幂公式。

  5. 循环变量写成 for (int p=2; p*p<=n; p++)
    注意循环条件中的 n 应该用临时变量 temp，因为 n 在除法中会变化。如果直接用原 n，循环次数会减少，可能漏掉因子。

完整示例与运行结果

以 n=36 为例：

  • 分解质因数：36 = 2² × 3²
  • φ(36) = 36 × (1-1/2) × (1-1/3) = 36 × 1/2 × 2/3 = 12
  • 程序运行：
请输入一个正整数 n: 36
φ(36) = 12

再试一个大的：n=1000000007（质数），应输出 φ = 1000000006。

相关知识点指引

现在你已经能快速计算单个数的欧拉函数了。接下来可以学：

  • 线性筛求欧拉函数：如果需要计算1到N的所有欧拉函数，可以用线性筛一次求出，复杂度 O(N)，效率极高。
  • 欧拉定理：如果 a 和 n 互质，那么 a^{φ(n)} ≡ 1 (mod n)。这是RSA加密的基础。
  • 扩展欧几里得：可以求模逆元，与欧拉函数配合使用。
  • 大数分解与Pollard Rho：如果 n 非常大（比如10^18），上面的试除法就不够了，需要更高级的分解算法。

欧拉函数是数论入门的关键一步，弄懂了它，你就能轻松理解很多加密算法和数学竞赛题。现在动手试一试，用代码算出你的学号（或者生日）的欧拉函数吧！

例题精讲

1单选题

关于欧拉函数的性质，以下说法错误的是？

A若n是质数，则φ(n)=n-1
B若a和b互质，则φ(ab)=φ(a)φ(b)
C对于任意正整数a,b，都有φ(ab)=φ(a)φ(b)
D若p是质数，k≥1，则φ(p^k)=p^k - p^{k-1}
2单选题

计算欧拉函数φ(360)的值为？

A96
B144
C192
D72
3判断题

欧拉函数满足：若p是质数，k≥1，则φ(p^k)=p^k - p^{k-1}。

4判断题

对于任意正整数n，欧拉函数φ(n)的值总是偶数。

5填空题
请补全以下用于计算欧拉函数的代码，利用质因数分解与公式φ(n)=n∏_{p|n}(1-1/p)。

int euler_phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            res -= ___;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}