1. 从一道面试题说起为什么需要“欧拉函数模板”最近在帮朋友准备算法面试他给我看了一道高频的题目大意是给定一个正整数n要求计算1到n之间有多少个数与n互质。他吭哧吭哧写了个循环对每个数都去求一次最大公约数gcd(i, n)如果等于1就计数。当n比较小的时候比如n10这方法没问题。但题目给的n范围是1 n 10^9甚至更大。他那个O(n log n)的算法直接超时当场就懵了。我告诉他这道题考的核心根本不是暴力枚举而是一个数论里的经典工具——欧拉函数。欧拉函数φ(n)的定义就是小于等于n的正整数中与n互质的数的个数。题目问的其实就是φ(n)的值。而计算φ(n)如果直接用定义去数和暴力没区别。真正高效的方法是利用欧拉函数的几个核心性质和计算公式将时间复杂度降到O(√n)。在实际的算法竞赛、密码学应用或者处理大数相关的业务逻辑时一个高效、鲁棒的欧拉函数实现就像一把瑞士军刀必不可少。今天我们就来彻底拆解这个“欧拉函数模板”不仅给你代码更要讲清楚背后的数学原理、不同场景下的实现变体以及那些容易踩进去的坑。2. 欧拉函数的数学基石从定义到计算公式要写出好用的模板不能只当“调包侠”得先明白它到底在算什么。欧拉函数φ(n)也叫Euler‘s totient function。它的定义很直观φ(n) #{k: 1 ≤ k ≤ n, gcd(k, n) 1}。比如φ(8) 4因为1, 3, 5, 7这四个数与8互质。但定义无法用于高效计算。欧拉函数的威力源于它的三个核心性质性质一积性函数。如果两个正整数a和b互质即gcd(a, b) 1那么φ(a*b) φ(a) * φ(b)。这个性质允许我们将一个大数n分解成多个互质的因子分别计算后再相乘极大地简化了问题。性质二质数的欧拉函数。如果p是一个质数那么φ(p) p - 1。这很好理解因为对于一个质数p从1到p-1的所有数都与它互质。性质三质数幂的欧拉函数。如果p是质数k是正整数那么φ(p^k) p^k - p^(k-1) p^(k-1) * (p - 1)。这是因为在1到p^k这些数中只有那些包含因子p的数才不与p^k互质这样的数有p^(k-1)个即p, 2p, 3p, ..., p^k所以互质的数就是总数减去这些。基于这三个性质我们可以推导出欧拉函数的通用计算公式。任何一个大于1的正整数n都可以进行质因数分解n p1^k1 * p2^k2 * ... * pm^km其中pi是质数ki是正整数。由于不同的质数幂之间是互质的根据积性函数性质φ(n) φ(p1^k1) * φ(p2^k2) * ... * φ(pm^km)再根据质数幂的性质将每个φ(pi^ki)替换为pi^(ki-1) * (pi - 1)φ(n) [p1^(k1-1) * (p1 - 1)] * [p2^(k2-1) * (p2 - 1)] * ... * [pm^(km-1) * (pm - 1)]这个式子可以进一步整理成更紧凑的形式。把每个pi^(ki-1)和前面的pi合并考虑可以得到最常用的计算公式φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)这个公式是模板代码的灵魂。它告诉我们计算φ(n)的核心步骤其实就是对n进行质因数分解找出所有不同的质因子p然后套用这个连乘公式。注意这里有一个非常关键的细节公式中(1 - 1/pi)是针对不同的质因子。比如n122^2*3我们只乘(1-1/2)和(1-1/3)而不是乘两次(1-1/2)。在代码实现时我们通常会在分解质因数的过程中每找到一个质因子p就让n不断除以p直到不能再除这样就去掉了该质因子的所有幂次然后给结果乘上(p-1)。但等一下这里又涉及到一个更高效的写法我们会在后面的模板部分详细解释。3. 单次求值模板O(√n)的经典实现理解了公式我们就可以动手写代码了。最常用、也是最基础的场景是给定一个n求φ(n)。下面给出这个场景下的标准模板并逐行解析。// 函数功能计算欧拉函数 φ(n) // 时间复杂度O(√n) long long euler_phi(long long n) { long long ans n; // 初始化为 n对应公式中的 n long long temp n; // 用一个临时变量操作 n避免修改原值 // 遍历所有可能的小于等于 √temp 的因子 for (long long p 2; p * p temp; p) { // 如果 p 是 temp 的因子那么 p 一定是质数 if (temp % p 0) { // 找到了一个质因子 p根据公式 ans ans / p * (p-1) // 这里先除后乘是为了防止中间结果溢出但更常见的写法是下面这种 ans ans / p * (p - 1); // 将 temp 中所有的因子 p 除尽 while (temp % p 0) { temp / p; } } } // 循环结束后temp 可能大于 1。此时 temp 一定是大于 √n 的质因子且仅有一个 // 例如 n13循环不会进入temp13它是一个质数需要处理 if (temp 1) { ans ans / temp * (temp - 1); } return ans; }代码逻辑深度解析初始化ans n对应公式φ(n) n * Π(1 - 1/p)中的初始n。质因数分解循环for (long long p 2; p * p temp; p)这是标准的试除法分解质因数。为什么循环条件是p * p temp因为一个合数temp至少有一个不大于其平方根的质因子。我们不断用找到的因子去除temp所以temp会越来越小。当temp被除到小于p*p时它要么是1要么是一个大于当前p的质数。找到质因子后的操作if (temp % p 0)当p能整除当前的temp时p一定是temp的一个质因子。为什么因为我们的循环是从2开始的并且内层while循环会把temp中所有p的因子都除掉。所以当再次遇到temp % p 0时这个p不可能是之前某个质因子的倍数否则早被除掉了它自己就是一个新的质因子。ans ans / p * (p - 1);这行代码是公式ans * (1 - 1/p)的等价变形。ans / p * (p-1)等于ans * (p-1)/p也就是ans * (1 - 1/p)。先除后乘可以在一定程度上避免整数溢出但前提是ans能被p整除这由数学性质保证因为p是n的因子而ans初始为n且在计算过程中始终是n乘以若干个分数结构上依然保持n的因子关系。while (temp % p 0) temp / p;这步至关重要它去掉了temp中所有p的幂次。这保证了我们找到的每个p都是不同的质因子并且后续的循环不会再处理这个p的倍数。这正是实现公式中“对不同质因子连乘”的关键。处理剩余的大质因子循环结束后如果temp 1那么此时的temp一定是n的一个质因子并且它大于原始的√n。因为如果它是合数它必然包含一个小于等于其平方根的因子而这个因子也必然小于等于原始的√n应该在之前的循环中被找到并除尽了。所以它一定是一个质数。我们需要对它进行同样的操作ans ans / temp * (temp - 1);。时间复杂度分析主要的开销在于for循环循环次数最多为√n级别尽管temp在减小但最坏情况下n本身是个大质数我们需要遍历2到√n的所有数才能确认。因此单次计算φ(n)的时间复杂度是O(√n)。对于n 10^12的情况这个复杂度通常是可接受的。4. 区间预处理模板埃氏筛与欧拉筛的妙用单次求值O(√n)很快但如果题目需要频繁查询比如求φ(1)到φ(N)的所有值或者需要多次计算不同n的欧拉函数每次都去分解质因数就不划算了。这时我们需要预处理出一定范围内所有数的欧拉函数值。这通常借助筛法来完成主要有两种思路埃拉托斯特尼筛法埃氏筛和线性筛欧拉筛。4.1 基于埃氏筛的O(N log log N)预处理埃氏筛的思想可以巧妙地用来计算欧拉函数。我们初始化一个数组phi[]令phi[i] i。然后我们模仿找质数的过程遍历所有数。// 函数功能用埃氏筛法预处理 [1, N] 的欧拉函数 // 时间复杂度O(N log log N)空间复杂度O(N) const int MAXN 1000000; // 预处理范围 long long phi[MAXN 5]; void euler_phi_sieve_eratosthenes(int N) { // 初始化 for (int i 1; i N; i) { phi[i] i; } // 遍历所有数 for (int i 2; i N; i) { // 如果 phi[i] i说明 i 是质数因为只有质数在初始化后还没被更新过 if (phi[i] i) { // 对于质数 i其欧拉函数值为 i-1 // phi[i] i - 1; // 这一步可以合并到下面的循环中 // 遍历所有 i 的倍数 j for (int j i; j N; j i) { // 根据公式 φ(n) n * Π(1 - 1/p)对于 j 来说i 是它的一个质因子 // 所以 phi[j] 需要先除以 i再乘以 (i-1) phi[j] phi[j] / i * (i - 1); } } } }原理与注意事项外层循环i从2到N。当phi[i] i时意味着i还没有被任何比它小的质数筛过因此i一定是质数。对于一个质数i我们遍历它的所有倍数j。对于每个ji都是它的一个质因子。根据欧拉函数公式φ(n) n * Π(1 - 1/p)我们需要对phi[j]初始值为j乘上(1 - 1/i)即phi[j] phi[j] * (i-1) / i。代码中写成先除后乘phi[j] / i * (i-1)是等价的并且能保证整除。这个算法为什么正确因为每个合数j都会被它的每一个质因子i处理一次并且处理的顺序无关紧要乘法满足交换律。最终phi[j]就变成了j * Π(1 - 1/p)正是欧拉函数的值。复杂度这个算法的时间复杂度与埃氏筛类似为O(N log log N)对于N在10^7量级时非常高效。但有一个小坑在j循环中我们是从j i开始的这包括了i本身。对于质数iphi[i]会在这次循环中被更新为i / i * (i-1) i-1。所以前面代码中注释掉的phi[i] i-1其实是不需要的。4.2 基于线性筛欧拉筛的O(N)预处理埃氏筛已经很快但线性筛能做到真正的O(N)并且在某些内存访问模式上更优。线性筛的核心是保证每个合数只被它的最小质因子筛掉一次。利用这个性质我们可以在筛的同时递推求出欧拉函数。// 函数功能用线性筛法预处理 [1, N] 的欧拉函数同时得到质数表 // 时间复杂度O(N)空间复杂度O(N) const int MAXN 1000000; int phi[MAXN 5]; // 欧拉函数值 int primes[MAXN 5]; // 质数表 bool is_prime[MAXN 5]; // 标记是否为质数初始全为 true int cnt 0; // 质数个数 void euler_phi_sieve_linear(int N) { // 初始化 for (int i 2; i N; i) { is_prime[i] true; } phi[1] 1; // 定义 φ(1) 1 // 线性筛主体 for (int i 2; i N; i) { if (is_prime[i]) { primes[cnt] i; // i 是质数加入质数表 phi[i] i - 1; // 质数的欧拉函数值 } // 遍历当前已知的所有质数 for (int j 0; j cnt; j) { long long next (long long)i * primes[j]; if (next N) break; // 超过范围跳出 is_prime[next] false; // 用最小质因子 primes[j] 筛掉合数 next // *** 核心根据 i 和 primes[j] 的关系递推 phi[next] *** if (i % primes[j] 0) { // 情况一primes[j] 是 i 的质因子 // 那么 primes[j] 也是 next 的质因子且不是新的质因子 // 公式φ(next) φ(i) * primes[j] phi[next] phi[i] * primes[j]; break; // 保证每个合数只被最小质因子筛一次 } else { // 情况二primes[j] 不是 i 的质因子 // 那么 primes[j] 是 next 的最小质因子且与 i 互质 // 根据积性函数性质φ(next) φ(i) * φ(primes[j]) φ(i) * (primes[j] - 1) phi[next] phi[i] * (primes[j] - 1); } } } }递推原理的详细证明这是理解模板的关键线性筛在标记合数next i * primes[j]时primes[j]一定是next的最小质因子。我们根据i是否包含primes[j]这个因子分两种情况推导φ(next)i % primes[j] 0这意味着primes[j]是i的一个质因子。设i primes[j]^k * m其中m与primes[j]互质。那么next i * primes[j] primes[j]^(k1) * m。计算φ(i)φ(i) φ(primes[j]^k) * φ(m) [primes[j]^(k-1) * (primes[j]-1)] * φ(m)。计算φ(next)φ(next) φ(primes[j]^(k1)) * φ(m) [primes[j]^k * (primes[j]-1)] * φ(m)。对比两者φ(next) φ(i) * primes[j]。直观理解next相比i只是多乘了一个已有的质因子primes[j]并没有引入新的质因子。根据公式φ(n)n*Π(1-1/p)next的质因子集合与i相同所以φ(next)/next φ(i)/i。又因为next i * primes[j]所以φ(next) (φ(i)/i) * next φ(i) * primes[j]。i % primes[j] ! 0这意味着primes[j]不是i的因子。由于primes[j]是质数所以gcd(i, primes[j]) 1即i与primes[j]互质。根据欧拉函数的积性性质对于互质的两个数a和b有φ(a*b) φ(a) * φ(b)。所以φ(next) φ(i * primes[j]) φ(i) * φ(primes[j]) φ(i) * (primes[j] - 1)。break的作用在线性筛中当i % primes[j] 0时必须break。这是因为此时primes[j]已经是i的最小质因子。对于下一个更大的质数primes[j1]next i * primes[j1]的最小质因子应该是primes[j]而不是primes[j1]因为i包含了primes[j]。如果继续循环就会用非最小质因子去筛数破坏了“每个合数只被最小质因子筛一次”的规则可能导致phi[]被错误计算多次。提示线性筛求欧拉函数的模板非常经典且高效建议理解并记忆。在需要一次性处理大量欧拉函数查询或者需要同时用到质数表和欧拉函数值的题目中比如某些莫比乌斯反演、狄利克雷卷积的题目这个模板是首选。5. 模板的变体、边界与实战踩坑点掌握了基础的单点求值和区间预处理模板我们还需要了解一些常见的变体和必须注意的边界条件这些都是实战中容易出错的地方。5.1 需要返回质因数分解结果的变体有些题目不仅需要φ(n)还需要知道n的质因数分解形式。我们可以稍微修改单点求值函数使其在计算过程中收集质因子。// 变体计算欧拉函数并返回质因子列表 long long euler_phi_with_factors(long long n, vectorlong long factors) { long long ans n; long long temp n; factors.clear(); // 清空传入的vector for (long long p 2; p * p temp; p) { if (temp % p 0) { factors.push_back(p); // 记录质因子 ans ans / p * (p - 1); while (temp % p 0) temp / p; } } if (temp 1) { factors.push_back(temp); // 记录剩余的大质因子 ans ans / temp * (temp - 1); } return ans; }这个变体在解决一些更复杂的数论问题时很有用比如求n的原根就需要知道φ(n)的所有质因子。5.2 处理n1的边界情况这是一个非常容易忽略的坑根据定义φ(1) 1因为1和1的最大公约数是1且小于等于1的正整数只有1本身。但在我们的单点求值模板中如果输入n1for循环条件p*p temp初始就不满足2*2 1会直接跳到最后的if(temp1)判断此时temp1不大于1所以函数返回初始值ansn1。看起来结果是正确的但过程是巧合。更严谨的写法应该在函数开头显式处理n1的情况long long euler_phi(long long n) { if (n 1) return 1; // 显式处理边界 long long ans n; // ... 其余代码不变 }对于预处理模板线性筛我们通常会在初始化时设置phi[1] 1。5.3 大整数与溢出问题当n很大比如接近10^18时我们的单点求值模板中的p * p temp可能会溢出即使p和temp都是long long。例如当p很大时大于2^31p * p可能会超过64位有符号整数的范围导致溢出为负数从而使循环条件误判。更安全的写法是for (long long p 2; p temp / p; p) { // 用除法代替乘法判断 if (temp % p 0) { // ... } }同样在计算ans ans / p * (p - 1)时虽然数学上ans能被p整除但在代码执行过程中ans可能已经因为之前的连乘连除而变得很大或很小。如果题目对模数有要求比如结果要对一个大质数取模我们就不能直接使用整数除法而需要使用模逆元来计算ans ans * (p-1) * inv(p) % MOD其中inv(p)是p在模MOD意义下的乘法逆元。这是数论题中另一个常见的坑点。5.4 性能优化使用质数表进行试除在单点求值中我们循环p从2到√n。实际上我们只需要用质数去试除就够了。如果n很大且我们需要多次调用单点求值函数可以先用线性筛预处理出一个sqrt(MAX_N)范围内的质数表然后在求值函数中只用这些质数去试除可以显著减少循环次数。// 假设已经用线性筛得到了 primes[] 数组和 cnt long long euler_phi_fast(long long n, const int primes[], int cnt) { if (n 1) return 1; long long ans n; long long temp n; for (int i 0; i cnt; i) { long long p primes[i]; if (p * p temp) break; // 质数的平方大于当前temp终止 if (temp % p 0) { ans ans / p * (p - 1); while (temp % p 0) temp / p; } } if (temp 1) { ans ans / temp * (temp - 1); } return ans; }这个优化在n很大且随机时效果明显因为大部分合数在很小的质数阶段就被分解了。6. 实战应用场景与题目分析欧拉函数模板不是孤立的它常常作为子模块嵌入到更复杂的问题中。下面看几个典型场景。场景一求解模运算下的乘法逆元费马小定理在模质数p的意义下如果a不是p的倍数则a的逆元a^(-1) ≡ a^(p-2) (mod p)。这里p-1就是φ(p)。更一般地根据欧拉定理如果gcd(a, n) 1则a^φ(n) ≡ 1 (mod n)。因此a在模n下的一个逆元是a^(φ(n)-1) mod n前提是a与n互质。计算a^b mod n需要快速幂而其中指数b就可能用到φ(n)。场景二RSA加密算法RSA公钥密码体系的核心计算中关键一步是选择两个大质数p和q计算n p*q以及φ(n) (p-1)*(q-1)。然后选择一个与φ(n)互质的整数e作为公钥再计算私钥d使得e*d ≡ 1 (mod φ(n))。这里φ(n)的计算是基础。虽然实际中p和q已知直接相乘即可但原理正是欧拉函数的积性。场景三数论函数求和问题有一类经典问题求∑_{i1}^{n} φ(i)或∑_{i1}^{n} gcd(i, n)。后者可以通过变形转化为欧拉函数求和∑_{d|n} d * φ(n/d)。解决这类问题往往需要预处理出φ(1)到φ(n)的所有值使用线性筛模板然后求前缀和。例如求∑_{i1}^{n} φ(i)预处理后直接累加即可O(1)查询。一道经典题目分析“计算1 i, j n的数对(i, j)中有多少对互质即gcd(i, j) 1” 暴力枚举是O(n^2)不可行。一个巧妙的解法是利用欧拉函数。固定j与j互质的i的个数就是φ(j)。所以答案就是∑_{j1}^{n} φ(j)。我们只需要用线性筛预处理出φ(1)...φ(n)并求和时间复杂度O(n)预处理后可以O(1)回答每个n的查询。7. 从模板到精通理解本质与举一反三最后我想分享几点从“会用模板”到“真正理解”的心得。第一理解“积性”是核心。欧拉函数是积性函数这是它能被高效计算的根本。许多数论函数如约数个数、约数和、莫比乌斯函数都是积性的。线性筛之所以强大就是因为它能在O(n)时间内预处理出所有积性函数的值。其核心递推逻辑根据最小质因子分情况讨论是相通的。如果你能彻底理解线性筛求欧拉函数的递推公式那么理解线性筛求莫比乌斯函数μ(n)、约数个数函数d(n)等就会容易得多。第二公式φ(n)n*Π(1-1/p)的直观意义。这个公式可以这样理解从1到n这n个数中先去掉所有p1的倍数比例是1/p1剩下n*(1-1/p1)个数再从剩下的数中去掉所有p2的倍数注意此时p2的倍数有些已经被p1去掉了但比例仍然是1/p2这是由容斥原理保证的剩下n*(1-1/p1)*(1-1/p2)个数……依次类推。这种“筛法”式的理解和代码实现中的连乘过程完美对应。第三关于“模板”的思考。本文给出了几个模板但切忌死记硬背。最重要的是掌握其背后的原理通过质因数分解利用积性函数性质和计算公式。单点求值的本质是试除法分解质因数埃氏筛预处理是模拟了每个质因子去筛它的倍数线性筛预处理则是利用最小质因子进行动态递推。当你遇到一个变种问题比如需要计算∑ φ(d)d是n的约数你知道它等于n本身这是一个重要性质你就能灵活应对而不是去生搬硬套某个模板。在实际编码中我个人的习惯是如果只需要单次或少量计算就用单点求值函数并加上质数表优化如果预计算质数表方便的话如果需要频繁查询区间内的欧拉函数值或者需要同时用到质数表那就毫不犹豫地使用线性筛预处理模板。它代码稍长但一次构建终身受益在复杂的数论问题中尤其省心。