我的算法书 - 欧拉函数

一句话算法

欧拉函数 $\varphi(n)$ 统计 $1$ 到 $n$ 中有多少个数与 $n$ 互质。

问题模型

给定一个正整数 $n$ ，求：

\varphi(n)=|\{x\mid 1\le x\le n,\gcd(x,n)=1\}|

例如 $n=6$ 时， $1,5$ 与 $6$ 互质，所以：

\varphi(6)=2

核心直觉

一个数 $x$ 与 $n$ 不互质，当且仅当它被 $n$ 的某个质因子整除。

如果：

n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

那么要从 $1..n$ 中删掉所有被 $p_1,p_2,\ldots,p_k$ 整除的数。用容斥整理后得到公式：

\varphi(n)=n\prod_{i=1}^{k}\left(1-\frac1{p_i}\right)

注意，公式只关心“有哪些不同质因子”，不关心每个质因子的次数。

算法步骤

令答案 ans = n。
从 p = 2 开始试除到 $\sqrt n$ 。
如果 p 能整除当前 n：
- 说明 p 是原数的一个质因子；
- 更新 ans = ans / p * (p - 1)；
- 把当前 n 中所有因子 p 除干净。
循环结束后，如果 n > 1，说明剩下一个大质因子，再做一次：
- ans = ans / n * (n - 1)。
输出 ans。

算法证明

设 $n$ 的不同质因子为 $p_1,p_2,\ldots,p_k$ 。

不互质的判定

$x$ 与 $n$ 不互质，等价于 $x$ 至少含有一个 $p_i$ 作为因子。
保留下来的比例

在 $1..n$ 中， $p_i$ 的倍数占 $\frac1{p_i}$ 。删掉这些倍数后，保留比例为：

$1-\frac1{p_i}$
多个质因子的容斥

对所有不同质因子做容斥，保留下来的数量为：

$n\prod_{i=1}^{k}\left(1-\frac1{p_i}\right)$
代码等价

对每个质因子 $p$ ，代码执行：

$ans \leftarrow ans\div p\times(p-1)$
这正是把当前答案乘上 $\left(1-\frac1p\right)$ 的整数写法。

所以算法正确计算了 $\varphi(n)$ 。

复杂度分析

试除法最多枚举到 $\sqrt n$ ，时间复杂度为 $O(\sqrt n)$ 。

空间复杂度为 $O(1)$ 。

如果需要求 $1..N$ 的所有欧拉函数值，应使用线性筛递推，不能对每个数单独试除。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

        #include <bits/stdc++.h>
using namespace std;

long long euler_phi(long long n) {
    long long ans = n;

    for (long long p = 2; p * p <= n; p++) {
        if (n % p != 0) continue;

        ans = ans / p * (p - 1);
        while (n % p == 0) n /= p;
    }

    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    cout << euler_phi(n) << '\n';
    return 0;
}

测试用例

输入：

输出：

解释：

36=2^2\times3^2

所以：

\varphi(36)=36\left(1-\frac12\right)\left(1-\frac13\right)=12

应用分类详解

欧拉函数的本质是统计模 $n$ 意义下的可逆元素数量。

一、互质计数

典型模式： 题目要求统计 $1..n$ 中与 $n$ 互质的数。

识别信号： 出现“互质个数”“小于等于 n 且 gcd 为 1”。

核心建模： 把 $n$ 分解质因子，套欧拉函数公式。

应用场景	经典题目	核心思路
单点互质计数	luogu-P2303	试除质因子求 $\varphi(n)$
互质对统计	luogu-P2158	枚举分母时用欧拉函数计数

二、模意义下的可逆元素

典型模式： 判断模 $n$ 下哪些数有乘法逆元。

识别信号： 出现“逆元”“剩余类”“与模数互质”。

核心建模： 模 $n$ 下有逆元的数正好是与 $n$ 互质的数，因此数量是 $\varphi(n)$ 。

应用场景	经典题目	核心思路
逆元存在性	模运算题	`gcd(a,n)=1` 才存在逆元
剩余类群大小	数论证明题	可逆剩余类个数为 $\varphi(n)$

三、欧拉定理与指数降幂

典型模式： 大指数取模，并且底数与模数互质。

识别信号： 出现 $a^b\bmod m$ ，指数极大，且需要利用周期。

核心建模： 若 $\gcd(a,m)=1$ ，则：

a^{\varphi(m)}\equiv1\pmod m

可以用 $\varphi(m)$ 处理指数周期。

应用场景	经典题目	核心思路
欧拉降幂	大指数取模题	先求 $\varphi(m)$ ，再处理指数
费马小定理	素数模数题	素数 $p$ 下 $\varphi(p)=p-1$

经典例题

1. luogu-P2303

单个数欧拉函数模板题。分解 $n$ 的不同质因子，每遇到一个质因子就执行 ans = ans / p * (p - 1)。

2. luogu-P2158

统计互质点对。核心是把每个分母对应的合法分子数量转化为欧拉函数值。

3. 欧拉降幂类题

当题目要求计算超大指数的 $a^b\bmod m$ ，并且可以保证 $\gcd(a,m)=1$ 时，欧拉定理给出指数周期 $\varphi(m)$ 。

参考

欧拉函数公式
欧拉定理