1. 项目概述从“互质”到“计数”的桥梁如果你在刷算法题时遇到过“求小于等于n且与n互质的数的个数”这类问题或者在学习RSA加密原理时对那个神秘的φ(n)符号感到好奇那么你正在接触的就是数论中的核心工具之一——欧拉函数。它远不止是一个冰冷的数学公式而是连接整数结构、密码学乃至算法竞赛的实用桥梁。简单来说欧拉函数 φ(n) 就是计算从1到n之间有多少个整数与n互质即最大公约数为1。这个看似简单的定义背后却蕴含着整数分解的深刻规律。在实际开发或学习中直接手算φ(n)效率低下我们需要的是理解其计算原理并掌握高效的编程实现。无论是解决“SDOI 2008 仪仗队”这样的经典数论问题还是理解非对称加密的基石欧拉函数都是必须跨越的一道坎。本文将从一个算法爱好者和实践者的角度带你彻底吃透欧拉函数的定义、多种计算方法、典型应用场景以及那些容易踩坑的细节。我们会从最基础的公式推导讲起逐步深入到线性筛法求欧拉函数这种高效算法并探讨其在模运算逆元求解和特定问题中的应用。无论你是正在备战信息学竞赛的学生还是对基础数论感兴趣的开发者这篇内容都将提供可直接“抄作业”的代码和清晰的思路。2. 欧拉函数的核心定义与性质解析2.1 互质概念的再审视与函数定义在深入欧拉函数之前我们必须夯实“互质”这个概念。两个整数a和b互质意味着它们的最大公约数 gcd(a, b) 1。注意互质描述的是两个数之间的关系而不是单个数的属性。例如8和15是互质的尽管它们各自都不是质数。欧拉函数 φ(n)也称为Euler‘s totient function其正式定义是对于正整数nφ(n) 表示小于等于n的正整数中与n互质的数的个数。这里有几个关键边界和特殊情况需要明确φ(1) 1。这是定义规定的因为1与自身互质且小于等于1的正整数只有1本身。如果n是质数p那么φ(p) p - 1。因为对于一个质数p从1到p-1的所有数都与p互质质数的定义决定了它只有1和自身两个正因数。φ(n) 的值总是小于等于n-1当且仅当n为质数时取等号。理解这个定义最直观的方式是举例。让我们计算几个小值n6小于等于6的数有1,2,3,4,5,6。与6互质的数需要满足gcd(k,6)1。6的质因数是2和3。因此排除2的倍数2,4,6和3的倍数3,6剩下的数是1和5。所以 φ(6) 2。n99的质因数是3。在1到9中排除3的倍数3,6,9剩下1,2,4,5,7,8。这6个数都与9互质所以 φ(9) 6。注意计算φ(n)时“小于等于n”这个条件包含n本身。但当n1时n与n本身的最大公约数是n必然不互质除非n1。所以对于n1我们实际上只需要考虑1到n-1这个范围。但在定义和某些公式推导中从1到n的完整区间表述更为严谨。2.2 支撑高效计算的三大核心性质欧拉函数的威力不仅在于定义更在于它几个优美的数学性质这些性质是我们设计高效算法的基础。性质一积性函数性质这是欧拉函数最重要的性质。如果两个正整数m和n互质即 gcd(m, n) 1那么 φ(m * n) φ(m) * φ(n)。这意味着对于一个大数如果我们能把它分解成几个两两互质的部分就可以分别计算这些部分的欧拉函数值再相乘极大地简化了计算。例如φ(35) φ(5 * 7)。由于5和7互质所以 φ(35) φ(5) * φ(7) 4 * 6 24。你可以验证在1到35中确实有24个数与35互质。性质二质数幂次的计算公式对于一个质数p的k次幂k ≥ 1即 n p^k其欧拉函数有直接公式φ(p^k) p^k - p^(k-1) p^(k-1) * (p - 1)。这个公式的直观理解是在1到 p^k 这 p^k 个数中与 p^k 不互质的数就是那些含有质因子p的数也就是p的倍数。p的倍数有多少个呢就是 p^k / p p^(k-1) 个。所以互质的数就有 p^k - p^(k-1) 个。例如φ(8) φ(2^3) 2^3 - 2^2 8 - 4 4。在1到8中与8不互质的数是2,4,6,8都是2的倍数剩下的1,3,5,7共4个数与8互质。性质三通用计算公式由前两个性质推导基于上述两个性质我们可以得到对于任意正整数n若其标准质因数分解为 n p1^a1 * p2^a2 * ... * pm^am其中pi是互不相同的质数那么欧拉函数的通用计算公式为 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)这个公式是实践中最常用的。它直接由积性性质和质数幂公式推导而来。推导过程φ(n) φ(p1^a1) * φ(p2^a2) * ... * φ(pm^am) [p1^a1 * (1 - 1/p1)] * [p2^a2 * (1 - 1/p2)] * ... n * (1 - 1/p1) * (1 - 1/p2) * ...。例如n12 2^2 * 3^1。那么 φ(12) 12 * (1 - 1/2) * (1 - 1/3) 12 * (1/2) * (2/3) 4。验证在1到12中与12互质的数是1,5,7,11共4个。实操心得通用公式是手算或单次查询时的首选。在编程中如果只需要计算单个n的φ值通常采用质因数分解结合此公式的方法时间复杂度约为O(√n)。但如果需要预处理出从1到N所有数的φ值就必须使用更高效的线性筛法我们会在后面详细讲解。3. 欧拉函数的计算方法与实现理解了定义和性质后我们需要掌握如何高效地计算φ(n)。根据不同的应用场景单次查询 vs 批量预处理选择合适的方法至关重要。3.1 基于质因数分解的单点计算法这是最直接的方法适用于只需要计算单个或少量n的φ值的情况。其核心步骤就是利用通用公式 φ(n) n * Π(1 - 1/p)。算法步骤初始化结果ans n。对n进行质因数分解。从i2开始遍历到√n。如果i能整除n说明i是n的一个质因子在遍历过程中由于我们总是先遇到质因子遇到合数因子时它早已被其质因子除尽所以此时的i一定是质数。执行ans ans / i * (i - 1)。这等价于ans ans * (1 - 1/i)但避免了浮点数运算保证了结果始终是整数。将n中所有i的因子除尽while (n % i 0) n / i;。遍历结束后如果n 1说明剩下的n本身是一个大于√n的质因子对结果进行同样的处理ans ans / n * (n - 1)。返回ans。代码实现C风格int euler_phi_single(int n) { int ans n; int temp n; // 保留n的副本进行操作 for (int i 2; i * i temp; i) { if (temp % i 0) { ans ans / i * (i - 1); // 先除后乘防止溢出 while (temp % i 0) temp / i; } } if (temp 1) { // 处理剩余的大质因子 ans ans / temp * (temp - 1); } return ans; }复杂度分析时间复杂度为O(√n)主要消耗在质因数分解的循环上。空间复杂度为O(1)。对于单次查询在n不超过10^12在64位整数范围内时这个算法是完全可以接受的。注意事项代码中ans ans / i * (i - 1)的顺序很重要。必须先进行除法ans / i确保结果是整数然后再乘(i-1)。如果写成ans ans * (i-1) / i虽然数学上等价但在编程中ans * (i-1)可能会发生整数溢出尤其是在ans和i都很大的时候。先除可以保证中间结果尽可能小。3.2 线性筛法批量预处理欧拉函数当问题需要频繁查询多个φ值或者需要用到1到N所有数的φ值时例如求和、求前缀和单点计算的O(N√N)总体复杂度是无法接受的。这时欧拉筛线性筛是唯一的选择它可以在O(N)的时间复杂度内同时筛出1到N的所有质数以及每个数的欧拉函数值。线性筛求欧拉函数的原理基于欧拉函数的积性性质并需要处理质数、质数乘以质数、合数乘以质数等多种情况。我们需要维护两个数组is_prime[]标记是否为质数phi[]存储欧拉函数值。算法核心与递推关系初始化phi[1] 1。对于质数pphi[p] p - 1。我们用筛法遍历每个数i并用已知的质数prime[j]去筛。关键递推公式分两种情况情况Ai % prime[j] 0。这意味着prime[j]是i的最小质因子。那么i * prime[j]这个数其质因子集合与i完全相同只是prime[j]的指数增加了1。根据公式 φ(n) n * Π(1 - 1/p)对于n i * prime[j]其质因子乘积部分变成了i * prime[j]而连乘部分 Π(1 - 1/p) 与i的完全相同。因此phi[i * prime[j]] phi[i] * prime[j]。情况Bi % prime[j] ! 0。这意味着prime[j]小于i的最小质因子且与i互质。根据积性函数性质phi[i * prime[j]] phi[i] * phi[prime[j]] phi[i] * (prime[j] - 1)。代码实现C风格const int MAXN 1000000; // 预处理范围 int prime[MAXN 5], phi[MAXN 5]; bool is_prime[MAXN 5]; int cnt 0; // 质数个数 void euler_sieve(int n) { // 初始化 for (int i 1; i n; i) is_prime[i] true; is_prime[1] false; phi[1] 1; // 特别规定 for (int i 2; i n; i) { if (is_prime[i]) { prime[cnt] i; phi[i] i - 1; // 质数的欧拉函数值 } // 用当前已得到的质数筛去合数 for (int j 1; j cnt i * prime[j] n; j) { is_prime[i * prime[j]] false; if (i % prime[j] 0) { // 情况Aprime[j]是i的最小质因子 phi[i * prime[j]] phi[i] * prime[j]; break; // 保证每个数只被其最小质因子筛掉一次这是线性复杂度的关键 } else { // 情况Bprime[j]与i互质 phi[i * prime[j]] phi[i] * (prime[j] - 1); } } } }算法优势与对比特性单点计算 (质因数分解)批量预处理 (线性筛)时间复杂度O(√n) 每次查询O(N) 预处理O(1) 查询空间复杂度O(1)O(N)适用场景查询次数极少或n极大需要大量查询或需要1~N全部φ值代码复杂度简单中等需理解递推关系实操心得线性筛中的break语句是保证算法线性的灵魂。当i % prime[j] 0时说明prime[j]已经是i的最小质因子。那么对于下一个更大的质数prime[j1]i * prime[j1]的最小质因子将是prime[j]而不是prime[j1]。如果继续用prime[j1]去筛这个数会在后面当i增长到(i * prime[j1]) / prime[j]时被其最小质因子prime[j]筛掉造成重复筛除。因此此时必须break确保每个合数只被其最小质因子筛一次。4. 欧拉函数的经典应用场景剖析欧拉函数不是象牙塔里的数学玩具它在计算机科学和密码学中有实实在在的、不可替代的应用。4.1 数论基石欧拉定理与费马小定理欧拉定理是欧拉函数最著名的推论若正整数a与n互质即 gcd(a, n) 1则 a^φ(n) ≡ 1 (mod n)。这个定理揭示了模运算下幂运算的周期性是RSA加密算法的理论基础之一。一个特例是当n为质数p时φ(p) p-1欧拉定理退化为费马小定理若p是质数且a不是p的倍数即 gcd(a, p)1则 a^(p-1) ≡ 1 (mod p)。费马小定理常用来检验一个数是否为质数费马素性测试也是求解模逆元的重要工具。应用示例快速计算模幂的余数计算 7^2023 mod 15 的余数。首先gcd(7, 15)1满足欧拉定理条件。计算 φ(15) φ(35) 15(1-1/3)*(1-1/5)8。根据欧拉定理7^8 ≡ 1 (mod 15)。将指数分解2023 8 * 252 7。因此7^2023 ≡ (7^8)^252 * 7^7 ≡ 1^252 * 7^7 ≡ 7^7 (mod 15)。现在只需要计算 7^7 mod 15可以通过快速幂轻松计算7^249≡4, 7^4≡4^216≡1, 7^77^4 * 7^2 * 7^1 ≡ 1 * 4 * 7 28 ≡ 13 (mod 15)。 所以7^2023 mod 15 13。如果没有欧拉定理简化指数直接计算将非常困难。4.2 密码学核心RSA加密算法中的关键角色RSA公钥加密算法严重依赖欧拉函数。其密钥生成步骤如下选择两个大质数p和q计算 n p * q。计算 n 的欧拉函数值φ(n) φ(p) * φ(q) (p-1) * (q-1)。这个φ(n)是绝对保密的是私钥的一部分。选择一个整数e满足 1 e φ(n)且 gcd(e, φ(n)) 1。e作为公钥的一部分发布。计算e对于模φ(n)的模逆元d即满足 e * d ≡ 1 (mod φ(n)) 的d。d作为私钥的一部分计算d的过程就需要用到φ(n)。公钥为 (n, e)私钥为 (n, d)。加密过程密文 C M^e mod n。 解密过程明文 M C^d mod n。其正确性依赖于欧拉定理。因为 d 是 e 模 φ(n) 的逆元所以 ed kφ(n) 1。解密时C^d ≡ (M^e)^d ≡ M^(ed) ≡ M^(kφ(n)1) ≡ (M^φ(n))^k * M ≡ 1^k * M ≡ M (mod n)。这里要求 M 与 n 互质在实际中通过填充方案保证。安全性的根源RSA的安全性基于“大数质因数分解”的困难性。攻击者知道公钥(n, e)但想得到私钥d必须知道φ(n) (p-1)(q-1)而这等价于分解n得到p和q。当p和q是几百位甚至上千位的质数时分解n在现有计算能力下是不可行的。4.3 算法竞赛实战求解模逆元与计数问题在算法竞赛和编程中欧拉函数常用于以下两类问题1. 求解模逆元在模运算中我们经常需要计算 (a / b) mod m。除法在模运算中没有直接定义需要转化为乘以其模逆元。b在模m下的逆元 b^(-1)是满足 b * b^(-1) ≡ 1 (mod m) 的整数。逆元存在的充要条件是 gcd(b, m) 1。 根据欧拉定理如果 gcd(b, m) 1那么 b^φ(m) ≡ 1 (mod m)。因此b^(φ(m)-1) 就是 b 的一个模逆元。即 b^(-1) ≡ b^(φ(m)-1) (mod m)。我们可以用快速幂算法高效计算。代码片段使用欧拉定理求逆元// 假设已通过函数 euler_phi(m) 计算出 φ(m) long long mod_inverse_euler(long long b, long long m) { if (std::gcd(b, m) ! 1) return -1; // 逆元不存在 long long phi_m euler_phi_single(m); // 计算φ(m) return fast_pow(b, phi_m - 1, m); // 快速幂计算 b^(φ(m)-1) mod m }当然更常用的求逆元方法是扩展欧几里得算法其时间复杂度更低O(log min(b, m))且不要求m是质数只要求互质。但欧拉定理提供了另一种理解角度。2. 互质计数问题这是欧拉函数的直接应用。例如经典问题“SDOI 2008 仪仗队”有一个NN的方阵左下角是(0,0)右上角是(N-1, N-1)。士兵站在整点坐标上。问从(0,0)点能看到多少名士兵不包括(0,0)本身一个士兵能被看到当且仅当他和(0,0)的连线之间没有其他士兵。 经过分析一个位于(x, y)的士兵能被看到等价于 gcd(x, y) 1。并且由于对称性我们只需要考虑第一象限x0, y0以及坐标轴上的点。问题转化为求满足 1 ≤ x, y ≤ N-1 且 gcd(x, y)1 的点对(x, y)的数量再加上坐标轴上的2(N-1)个点。 对于每一行x1 ≤ x ≤ N-1能与x互质的y的个数就是 φ(x)。所以总数为Σ_{x1}^{N-1} φ(x) * 2 2*(N-1)这里需要注意我们计算的是点对每个(x,y)和(y,x)在第一象限是对称的但坐标轴上的点单独计算。更严谨的从(0,0)出发斜率不同的视线。最终答案可以表示为3 2 * Σ_{i2}^{N-1} φ(i) 当N1时。这里3代表(0,1), (1,0), (1,1)这三个点。对于i从2到N-1每个φ(i)对应一条斜率唯一的视线上的点除了(0,0)和(i,i)且对称所以乘以2。// 预处理phi数组后计算答案 long long ans 0; for (int i 2; i n; i) { // 假设n是方阵大小 ans phi[i]; } ans ans * 2 3; // 当n1时 if (n 1) ans 0; // 边界情况这类问题直接考察对欧拉函数定义的理解和批量预处理欧拉函数的能力。5. 常见问题、边界处理与性能优化在实际编码和应用欧拉函数时会遇到一些典型的陷阱和性能瓶颈。这里记录下我踩过的坑和总结的技巧。5.1 典型陷阱与边界条件φ(1) 的值这是最容易出错的地方。根据定义φ(1) 1。但在某些递推或初始化时如果错误地认为φ(1)0会导致后续计算全部出错。在线性筛法中务必显式设置phi[1] 1。整数溢出问题在单点计算公式ans ans / i * (i - 1)中如前所述必须先除后乘。在线性筛法中phi[i * prime[j]] phi[i] * prime[j]或phi[i] * (prime[j] - 1)也可能溢出尤其是当N很大如1e7且使用32位整型时。通常竞赛环境或现代应用中我们会使用64位整型C中的long long来存储φ值特别是当需要计算φ值的前缀和时。互质条件的检查在应用欧拉定理a^φ(n) ≡ 1 (mod n)时前提条件是 gcd(a, n) 1。如果忽略这个条件直接使用会导致计算结果错误。例如计算 2^φ(4) mod 4。φ(4)2但 gcd(2,4)2≠1实际上 2^24 ≡ 0 (mod 4)而不是1。n0 或负数的处理欧拉函数通常定义在正整数上。在编程时如果输入可能为非正数需要添加防御性代码根据题目要求返回特定值如0或抛出异常。5.2 性能优化与进阶技巧预处理φ值的前缀和在很多问题中如仪仗队问题我们需要频繁计算 Σφ(i)。与其每次循环累加不如在预处理出phi数组后再计算一个前缀和数组sum_phi[i] sum_phi[i-1] phi[i]。这样查询区间和的时间复杂度就是O(1)。这是典型的“空间换时间”策略在算法竞赛中极其常见。long long sum_phi[MAXN]; for (int i 1; i N; i) { sum_phi[i] sum_phi[i-1] phi[i]; } // 查询 φ(a) φ(a1) ... φ(b) long long range_sum sum_phi[b] - sum_phi[a-1];结合其他数论函数筛法线性筛法非常强大可以在O(N)时间内同时筛出质数、欧拉函数、莫比乌斯函数、约数个数等多个数论函数。它们的递推逻辑类似只是公式不同。掌握这种“一筛多用”的技巧能一次性解决很多预处理问题大幅提升解题效率。大数的单点φ计算优化对于极大的n比如超过10^12使用O(√n)的质因数分解可能仍然较慢。可以结合米勒-拉宾素性测试和Pollard-Rho因数分解算法来加速大数的质因数分解过程从而快速计算φ(n)。但这属于更进阶的数论算法范畴。记忆化搜索如果问题需要计算大量离散的、不确定的n的φ值且n的范围很大无法全部预处理可以考虑使用记忆化搜索缓存。用一个哈希表如C的unordered_map存储已经计算过的(n, φ(n))对避免重复计算。这在某些动态规划或递归问题中可能有用。5.3 调试与验证方法当你写完欧拉函数的代码后如何验证其正确性小数据暴力验证对于N较小的情况比如N1000可以写一个最朴素的暴力程序对于每个i从1到i遍历判断互质关系来计算φ(i)与你的高效算法结果对比。这是最可靠的验证方法。int brute_phi(int n) { int cnt 0; for (int i 1; i n; i) { if (std::gcd(i, n) 1) cnt; } return cnt; }利用已知数列对比欧拉函数的前若干项是已知的1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ... (OEIS A000010)。可以输出你的程序计算出的前20个值进行比对。检验积性性质随机生成多对互质的数(m, n)检查是否满足 φ(m*n) φ(m) * φ(n)。检验通用公式对于随机生成的n用你的算法计算φ(n)再使用质因数分解可以用另一个独立函数和通用公式计算看结果是否一致。欧拉函数作为数论的基础构件其价值在于将复杂的互质计数问题转化为可计算的数学对象。从理解其定义和性质开始到掌握单点计算和线性筛法两种核心实现最后在欧拉定理、RSA和各类计数问题中见识其威力这条学习路径是清晰且实用的。我个人的体会是数论知识的学习一定要结合具体的编程实现和问题来解决在代码中调试在问题中深化理解这样才能真正内化为解决问题的能力。当你再遇到需要计算互质个数或处理模幂循环节的问题时欧拉函数就会成为你手中自然而有力的工具。
欧拉函数：从互质计数到RSA加密的核心算法详解
1. 项目概述从“互质”到“计数”的桥梁如果你在刷算法题时遇到过“求小于等于n且与n互质的数的个数”这类问题或者在学习RSA加密原理时对那个神秘的φ(n)符号感到好奇那么你正在接触的就是数论中的核心工具之一——欧拉函数。它远不止是一个冰冷的数学公式而是连接整数结构、密码学乃至算法竞赛的实用桥梁。简单来说欧拉函数 φ(n) 就是计算从1到n之间有多少个整数与n互质即最大公约数为1。这个看似简单的定义背后却蕴含着整数分解的深刻规律。在实际开发或学习中直接手算φ(n)效率低下我们需要的是理解其计算原理并掌握高效的编程实现。无论是解决“SDOI 2008 仪仗队”这样的经典数论问题还是理解非对称加密的基石欧拉函数都是必须跨越的一道坎。本文将从一个算法爱好者和实践者的角度带你彻底吃透欧拉函数的定义、多种计算方法、典型应用场景以及那些容易踩坑的细节。我们会从最基础的公式推导讲起逐步深入到线性筛法求欧拉函数这种高效算法并探讨其在模运算逆元求解和特定问题中的应用。无论你是正在备战信息学竞赛的学生还是对基础数论感兴趣的开发者这篇内容都将提供可直接“抄作业”的代码和清晰的思路。2. 欧拉函数的核心定义与性质解析2.1 互质概念的再审视与函数定义在深入欧拉函数之前我们必须夯实“互质”这个概念。两个整数a和b互质意味着它们的最大公约数 gcd(a, b) 1。注意互质描述的是两个数之间的关系而不是单个数的属性。例如8和15是互质的尽管它们各自都不是质数。欧拉函数 φ(n)也称为Euler‘s totient function其正式定义是对于正整数nφ(n) 表示小于等于n的正整数中与n互质的数的个数。这里有几个关键边界和特殊情况需要明确φ(1) 1。这是定义规定的因为1与自身互质且小于等于1的正整数只有1本身。如果n是质数p那么φ(p) p - 1。因为对于一个质数p从1到p-1的所有数都与p互质质数的定义决定了它只有1和自身两个正因数。φ(n) 的值总是小于等于n-1当且仅当n为质数时取等号。理解这个定义最直观的方式是举例。让我们计算几个小值n6小于等于6的数有1,2,3,4,5,6。与6互质的数需要满足gcd(k,6)1。6的质因数是2和3。因此排除2的倍数2,4,6和3的倍数3,6剩下的数是1和5。所以 φ(6) 2。n99的质因数是3。在1到9中排除3的倍数3,6,9剩下1,2,4,5,7,8。这6个数都与9互质所以 φ(9) 6。注意计算φ(n)时“小于等于n”这个条件包含n本身。但当n1时n与n本身的最大公约数是n必然不互质除非n1。所以对于n1我们实际上只需要考虑1到n-1这个范围。但在定义和某些公式推导中从1到n的完整区间表述更为严谨。2.2 支撑高效计算的三大核心性质欧拉函数的威力不仅在于定义更在于它几个优美的数学性质这些性质是我们设计高效算法的基础。性质一积性函数性质这是欧拉函数最重要的性质。如果两个正整数m和n互质即 gcd(m, n) 1那么 φ(m * n) φ(m) * φ(n)。这意味着对于一个大数如果我们能把它分解成几个两两互质的部分就可以分别计算这些部分的欧拉函数值再相乘极大地简化了计算。例如φ(35) φ(5 * 7)。由于5和7互质所以 φ(35) φ(5) * φ(7) 4 * 6 24。你可以验证在1到35中确实有24个数与35互质。性质二质数幂次的计算公式对于一个质数p的k次幂k ≥ 1即 n p^k其欧拉函数有直接公式φ(p^k) p^k - p^(k-1) p^(k-1) * (p - 1)。这个公式的直观理解是在1到 p^k 这 p^k 个数中与 p^k 不互质的数就是那些含有质因子p的数也就是p的倍数。p的倍数有多少个呢就是 p^k / p p^(k-1) 个。所以互质的数就有 p^k - p^(k-1) 个。例如φ(8) φ(2^3) 2^3 - 2^2 8 - 4 4。在1到8中与8不互质的数是2,4,6,8都是2的倍数剩下的1,3,5,7共4个数与8互质。性质三通用计算公式由前两个性质推导基于上述两个性质我们可以得到对于任意正整数n若其标准质因数分解为 n p1^a1 * p2^a2 * ... * pm^am其中pi是互不相同的质数那么欧拉函数的通用计算公式为 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)这个公式是实践中最常用的。它直接由积性性质和质数幂公式推导而来。推导过程φ(n) φ(p1^a1) * φ(p2^a2) * ... * φ(pm^am) [p1^a1 * (1 - 1/p1)] * [p2^a2 * (1 - 1/p2)] * ... n * (1 - 1/p1) * (1 - 1/p2) * ...。例如n12 2^2 * 3^1。那么 φ(12) 12 * (1 - 1/2) * (1 - 1/3) 12 * (1/2) * (2/3) 4。验证在1到12中与12互质的数是1,5,7,11共4个。实操心得通用公式是手算或单次查询时的首选。在编程中如果只需要计算单个n的φ值通常采用质因数分解结合此公式的方法时间复杂度约为O(√n)。但如果需要预处理出从1到N所有数的φ值就必须使用更高效的线性筛法我们会在后面详细讲解。3. 欧拉函数的计算方法与实现理解了定义和性质后我们需要掌握如何高效地计算φ(n)。根据不同的应用场景单次查询 vs 批量预处理选择合适的方法至关重要。3.1 基于质因数分解的单点计算法这是最直接的方法适用于只需要计算单个或少量n的φ值的情况。其核心步骤就是利用通用公式 φ(n) n * Π(1 - 1/p)。算法步骤初始化结果ans n。对n进行质因数分解。从i2开始遍历到√n。如果i能整除n说明i是n的一个质因子在遍历过程中由于我们总是先遇到质因子遇到合数因子时它早已被其质因子除尽所以此时的i一定是质数。执行ans ans / i * (i - 1)。这等价于ans ans * (1 - 1/i)但避免了浮点数运算保证了结果始终是整数。将n中所有i的因子除尽while (n % i 0) n / i;。遍历结束后如果n 1说明剩下的n本身是一个大于√n的质因子对结果进行同样的处理ans ans / n * (n - 1)。返回ans。代码实现C风格int euler_phi_single(int n) { int ans n; int temp n; // 保留n的副本进行操作 for (int i 2; i * i temp; i) { if (temp % i 0) { ans ans / i * (i - 1); // 先除后乘防止溢出 while (temp % i 0) temp / i; } } if (temp 1) { // 处理剩余的大质因子 ans ans / temp * (temp - 1); } return ans; }复杂度分析时间复杂度为O(√n)主要消耗在质因数分解的循环上。空间复杂度为O(1)。对于单次查询在n不超过10^12在64位整数范围内时这个算法是完全可以接受的。注意事项代码中ans ans / i * (i - 1)的顺序很重要。必须先进行除法ans / i确保结果是整数然后再乘(i-1)。如果写成ans ans * (i-1) / i虽然数学上等价但在编程中ans * (i-1)可能会发生整数溢出尤其是在ans和i都很大的时候。先除可以保证中间结果尽可能小。3.2 线性筛法批量预处理欧拉函数当问题需要频繁查询多个φ值或者需要用到1到N所有数的φ值时例如求和、求前缀和单点计算的O(N√N)总体复杂度是无法接受的。这时欧拉筛线性筛是唯一的选择它可以在O(N)的时间复杂度内同时筛出1到N的所有质数以及每个数的欧拉函数值。线性筛求欧拉函数的原理基于欧拉函数的积性性质并需要处理质数、质数乘以质数、合数乘以质数等多种情况。我们需要维护两个数组is_prime[]标记是否为质数phi[]存储欧拉函数值。算法核心与递推关系初始化phi[1] 1。对于质数pphi[p] p - 1。我们用筛法遍历每个数i并用已知的质数prime[j]去筛。关键递推公式分两种情况情况Ai % prime[j] 0。这意味着prime[j]是i的最小质因子。那么i * prime[j]这个数其质因子集合与i完全相同只是prime[j]的指数增加了1。根据公式 φ(n) n * Π(1 - 1/p)对于n i * prime[j]其质因子乘积部分变成了i * prime[j]而连乘部分 Π(1 - 1/p) 与i的完全相同。因此phi[i * prime[j]] phi[i] * prime[j]。情况Bi % prime[j] ! 0。这意味着prime[j]小于i的最小质因子且与i互质。根据积性函数性质phi[i * prime[j]] phi[i] * phi[prime[j]] phi[i] * (prime[j] - 1)。代码实现C风格const int MAXN 1000000; // 预处理范围 int prime[MAXN 5], phi[MAXN 5]; bool is_prime[MAXN 5]; int cnt 0; // 质数个数 void euler_sieve(int n) { // 初始化 for (int i 1; i n; i) is_prime[i] true; is_prime[1] false; phi[1] 1; // 特别规定 for (int i 2; i n; i) { if (is_prime[i]) { prime[cnt] i; phi[i] i - 1; // 质数的欧拉函数值 } // 用当前已得到的质数筛去合数 for (int j 1; j cnt i * prime[j] n; j) { is_prime[i * prime[j]] false; if (i % prime[j] 0) { // 情况Aprime[j]是i的最小质因子 phi[i * prime[j]] phi[i] * prime[j]; break; // 保证每个数只被其最小质因子筛掉一次这是线性复杂度的关键 } else { // 情况Bprime[j]与i互质 phi[i * prime[j]] phi[i] * (prime[j] - 1); } } } }算法优势与对比特性单点计算 (质因数分解)批量预处理 (线性筛)时间复杂度O(√n) 每次查询O(N) 预处理O(1) 查询空间复杂度O(1)O(N)适用场景查询次数极少或n极大需要大量查询或需要1~N全部φ值代码复杂度简单中等需理解递推关系实操心得线性筛中的break语句是保证算法线性的灵魂。当i % prime[j] 0时说明prime[j]已经是i的最小质因子。那么对于下一个更大的质数prime[j1]i * prime[j1]的最小质因子将是prime[j]而不是prime[j1]。如果继续用prime[j1]去筛这个数会在后面当i增长到(i * prime[j1]) / prime[j]时被其最小质因子prime[j]筛掉造成重复筛除。因此此时必须break确保每个合数只被其最小质因子筛一次。4. 欧拉函数的经典应用场景剖析欧拉函数不是象牙塔里的数学玩具它在计算机科学和密码学中有实实在在的、不可替代的应用。4.1 数论基石欧拉定理与费马小定理欧拉定理是欧拉函数最著名的推论若正整数a与n互质即 gcd(a, n) 1则 a^φ(n) ≡ 1 (mod n)。这个定理揭示了模运算下幂运算的周期性是RSA加密算法的理论基础之一。一个特例是当n为质数p时φ(p) p-1欧拉定理退化为费马小定理若p是质数且a不是p的倍数即 gcd(a, p)1则 a^(p-1) ≡ 1 (mod p)。费马小定理常用来检验一个数是否为质数费马素性测试也是求解模逆元的重要工具。应用示例快速计算模幂的余数计算 7^2023 mod 15 的余数。首先gcd(7, 15)1满足欧拉定理条件。计算 φ(15) φ(35) 15(1-1/3)*(1-1/5)8。根据欧拉定理7^8 ≡ 1 (mod 15)。将指数分解2023 8 * 252 7。因此7^2023 ≡ (7^8)^252 * 7^7 ≡ 1^252 * 7^7 ≡ 7^7 (mod 15)。现在只需要计算 7^7 mod 15可以通过快速幂轻松计算7^249≡4, 7^4≡4^216≡1, 7^77^4 * 7^2 * 7^1 ≡ 1 * 4 * 7 28 ≡ 13 (mod 15)。 所以7^2023 mod 15 13。如果没有欧拉定理简化指数直接计算将非常困难。4.2 密码学核心RSA加密算法中的关键角色RSA公钥加密算法严重依赖欧拉函数。其密钥生成步骤如下选择两个大质数p和q计算 n p * q。计算 n 的欧拉函数值φ(n) φ(p) * φ(q) (p-1) * (q-1)。这个φ(n)是绝对保密的是私钥的一部分。选择一个整数e满足 1 e φ(n)且 gcd(e, φ(n)) 1。e作为公钥的一部分发布。计算e对于模φ(n)的模逆元d即满足 e * d ≡ 1 (mod φ(n)) 的d。d作为私钥的一部分计算d的过程就需要用到φ(n)。公钥为 (n, e)私钥为 (n, d)。加密过程密文 C M^e mod n。 解密过程明文 M C^d mod n。其正确性依赖于欧拉定理。因为 d 是 e 模 φ(n) 的逆元所以 ed kφ(n) 1。解密时C^d ≡ (M^e)^d ≡ M^(ed) ≡ M^(kφ(n)1) ≡ (M^φ(n))^k * M ≡ 1^k * M ≡ M (mod n)。这里要求 M 与 n 互质在实际中通过填充方案保证。安全性的根源RSA的安全性基于“大数质因数分解”的困难性。攻击者知道公钥(n, e)但想得到私钥d必须知道φ(n) (p-1)(q-1)而这等价于分解n得到p和q。当p和q是几百位甚至上千位的质数时分解n在现有计算能力下是不可行的。4.3 算法竞赛实战求解模逆元与计数问题在算法竞赛和编程中欧拉函数常用于以下两类问题1. 求解模逆元在模运算中我们经常需要计算 (a / b) mod m。除法在模运算中没有直接定义需要转化为乘以其模逆元。b在模m下的逆元 b^(-1)是满足 b * b^(-1) ≡ 1 (mod m) 的整数。逆元存在的充要条件是 gcd(b, m) 1。 根据欧拉定理如果 gcd(b, m) 1那么 b^φ(m) ≡ 1 (mod m)。因此b^(φ(m)-1) 就是 b 的一个模逆元。即 b^(-1) ≡ b^(φ(m)-1) (mod m)。我们可以用快速幂算法高效计算。代码片段使用欧拉定理求逆元// 假设已通过函数 euler_phi(m) 计算出 φ(m) long long mod_inverse_euler(long long b, long long m) { if (std::gcd(b, m) ! 1) return -1; // 逆元不存在 long long phi_m euler_phi_single(m); // 计算φ(m) return fast_pow(b, phi_m - 1, m); // 快速幂计算 b^(φ(m)-1) mod m }当然更常用的求逆元方法是扩展欧几里得算法其时间复杂度更低O(log min(b, m))且不要求m是质数只要求互质。但欧拉定理提供了另一种理解角度。2. 互质计数问题这是欧拉函数的直接应用。例如经典问题“SDOI 2008 仪仗队”有一个NN的方阵左下角是(0,0)右上角是(N-1, N-1)。士兵站在整点坐标上。问从(0,0)点能看到多少名士兵不包括(0,0)本身一个士兵能被看到当且仅当他和(0,0)的连线之间没有其他士兵。 经过分析一个位于(x, y)的士兵能被看到等价于 gcd(x, y) 1。并且由于对称性我们只需要考虑第一象限x0, y0以及坐标轴上的点。问题转化为求满足 1 ≤ x, y ≤ N-1 且 gcd(x, y)1 的点对(x, y)的数量再加上坐标轴上的2(N-1)个点。 对于每一行x1 ≤ x ≤ N-1能与x互质的y的个数就是 φ(x)。所以总数为Σ_{x1}^{N-1} φ(x) * 2 2*(N-1)这里需要注意我们计算的是点对每个(x,y)和(y,x)在第一象限是对称的但坐标轴上的点单独计算。更严谨的从(0,0)出发斜率不同的视线。最终答案可以表示为3 2 * Σ_{i2}^{N-1} φ(i) 当N1时。这里3代表(0,1), (1,0), (1,1)这三个点。对于i从2到N-1每个φ(i)对应一条斜率唯一的视线上的点除了(0,0)和(i,i)且对称所以乘以2。// 预处理phi数组后计算答案 long long ans 0; for (int i 2; i n; i) { // 假设n是方阵大小 ans phi[i]; } ans ans * 2 3; // 当n1时 if (n 1) ans 0; // 边界情况这类问题直接考察对欧拉函数定义的理解和批量预处理欧拉函数的能力。5. 常见问题、边界处理与性能优化在实际编码和应用欧拉函数时会遇到一些典型的陷阱和性能瓶颈。这里记录下我踩过的坑和总结的技巧。5.1 典型陷阱与边界条件φ(1) 的值这是最容易出错的地方。根据定义φ(1) 1。但在某些递推或初始化时如果错误地认为φ(1)0会导致后续计算全部出错。在线性筛法中务必显式设置phi[1] 1。整数溢出问题在单点计算公式ans ans / i * (i - 1)中如前所述必须先除后乘。在线性筛法中phi[i * prime[j]] phi[i] * prime[j]或phi[i] * (prime[j] - 1)也可能溢出尤其是当N很大如1e7且使用32位整型时。通常竞赛环境或现代应用中我们会使用64位整型C中的long long来存储φ值特别是当需要计算φ值的前缀和时。互质条件的检查在应用欧拉定理a^φ(n) ≡ 1 (mod n)时前提条件是 gcd(a, n) 1。如果忽略这个条件直接使用会导致计算结果错误。例如计算 2^φ(4) mod 4。φ(4)2但 gcd(2,4)2≠1实际上 2^24 ≡ 0 (mod 4)而不是1。n0 或负数的处理欧拉函数通常定义在正整数上。在编程时如果输入可能为非正数需要添加防御性代码根据题目要求返回特定值如0或抛出异常。5.2 性能优化与进阶技巧预处理φ值的前缀和在很多问题中如仪仗队问题我们需要频繁计算 Σφ(i)。与其每次循环累加不如在预处理出phi数组后再计算一个前缀和数组sum_phi[i] sum_phi[i-1] phi[i]。这样查询区间和的时间复杂度就是O(1)。这是典型的“空间换时间”策略在算法竞赛中极其常见。long long sum_phi[MAXN]; for (int i 1; i N; i) { sum_phi[i] sum_phi[i-1] phi[i]; } // 查询 φ(a) φ(a1) ... φ(b) long long range_sum sum_phi[b] - sum_phi[a-1];结合其他数论函数筛法线性筛法非常强大可以在O(N)时间内同时筛出质数、欧拉函数、莫比乌斯函数、约数个数等多个数论函数。它们的递推逻辑类似只是公式不同。掌握这种“一筛多用”的技巧能一次性解决很多预处理问题大幅提升解题效率。大数的单点φ计算优化对于极大的n比如超过10^12使用O(√n)的质因数分解可能仍然较慢。可以结合米勒-拉宾素性测试和Pollard-Rho因数分解算法来加速大数的质因数分解过程从而快速计算φ(n)。但这属于更进阶的数论算法范畴。记忆化搜索如果问题需要计算大量离散的、不确定的n的φ值且n的范围很大无法全部预处理可以考虑使用记忆化搜索缓存。用一个哈希表如C的unordered_map存储已经计算过的(n, φ(n))对避免重复计算。这在某些动态规划或递归问题中可能有用。5.3 调试与验证方法当你写完欧拉函数的代码后如何验证其正确性小数据暴力验证对于N较小的情况比如N1000可以写一个最朴素的暴力程序对于每个i从1到i遍历判断互质关系来计算φ(i)与你的高效算法结果对比。这是最可靠的验证方法。int brute_phi(int n) { int cnt 0; for (int i 1; i n; i) { if (std::gcd(i, n) 1) cnt; } return cnt; }利用已知数列对比欧拉函数的前若干项是已知的1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ... (OEIS A000010)。可以输出你的程序计算出的前20个值进行比对。检验积性性质随机生成多对互质的数(m, n)检查是否满足 φ(m*n) φ(m) * φ(n)。检验通用公式对于随机生成的n用你的算法计算φ(n)再使用质因数分解可以用另一个独立函数和通用公式计算看结果是否一致。欧拉函数作为数论的基础构件其价值在于将复杂的互质计数问题转化为可计算的数学对象。从理解其定义和性质开始到掌握单点计算和线性筛法两种核心实现最后在欧拉定理、RSA和各类计数问题中见识其威力这条学习路径是清晰且实用的。我个人的体会是数论知识的学习一定要结合具体的编程实现和问题来解决在代码中调试在问题中深化理解这样才能真正内化为解决问题的能力。当你再遇到需要计算互质个数或处理模幂循环节的问题时欧拉函数就会成为你手中自然而有力的工具。