欧拉函数

前言

在 02-01 整数与整除 里我们学了 GCD，在 02-02 素数与筛法 里学了筛法。现在把两者结合：给定 $N$，1 到 $N$ 中有多少个和 $N$ 互质的数？

这个数量叫欧拉函数 $\varphi(N)$。它不只是个数学定义——费马小定理的推广（欧拉定理）需要它，模意义下求逆元需要它，计算原根个数也需要它。

问题的本质

定义

$\varphi(N)$ = $\{1, 2, \ldots, N\}$ 中与 $N$ 互质（$\gcd(k, N) = 1$）的数的个数。

手动算几个：

$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
7	{1,2,3,4,5,6}	6
12	{1,5,7,11}	4

有什么规律？素数 $p$ 的欧拉函数是 $p-1$——因为 1 到 $p-1$ 都和 $p$ 互质。$p^2$ 的欧拉函数是 $p^2-p$——因为 1 到 $p^2$ 中只有 $p$ 的倍数不互质，有 $p$ 个。

唯一分解与公式

由算术基本定理，$N = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$。则：

$$\varphi(N) = N \prod_{p \mid N} \left(1 - \frac{1}{p}\right) = N \prod_{p \mid N} \frac{p-1}{p}$$

直觉理解：在 1 到 $N$ 中，是 $p$ 的倍数的占 $1/p$，所以不是 $p$ 的倍数的占 $(1-1/p)$。多个素因子独立（因为素数两两互质），所以乘起来。

验证：$N=12=2^2 \times 3$。$\varphi(12) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$。✓

积性

$\varphi$ 是积性函数：如果 $\gcd(a,b)=1$，则 $\varphi(ab) = \varphi(a) \times \varphi(b)$。

这意味着：只要能算 $\varphi(p^k)$，就能算任意 $N$ 的欧拉函数。

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$。

理论 + 代码

单点计算 $O(\sqrt{N})$

long long euler_phi(long long n) {
    long long ans = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            ans = ans / p * (p - 1);    // ① 乘 (p-1)/p
            while (n % p == 0) n /= p;  // ② 去掉所有 p 因子
        }
    }
    if (n > 1) ans = ans / n * (n - 1); // ③ 剩下的大于√n 的素因子
    return ans;
}

• ① ans / p * (p-1)：先除后乘防溢出。
• ② 除干净——因为同一个素因子只处理一次。
• ③ 如果 $n$ 还剩一个大于 $\sqrt{N}$ 的素因子（比如 $N=14=2\times7$，处理完 2 后 $n=7$）。

走一遍过程：$\varphi(60)$。$60 = 2^2 \times 3 \times 5$。

• $p=2$：ans = 60/2*(2-1) = 30，$n$ 变为 15。
• $p=3$：ans = 30/3*(3-1) = 20，$n$ 变为 5。
• $p=5$：5*5=25 > 5，循环结束。
• $n=5>1$：ans = 20/5*(5-1) = 16。

$\varphi(60)=16$。验证：$60=2^2\times3\times5$，$60\times\frac{1}{2}\times\frac{2}{3}\times\frac{4}{5}=16$。✓

筛法求所有 $\varphi(1)$ 到 $\varphi(N)$——$O(N \log \log N)$

类似 02-02 素数与筛法 中的欧拉筛：

int phi[1000006];
void euler_sieve(int N) {
    for (int i = 0; i <= N; i++) phi[i] = i;
    for (int i = 2; i <= N; i++) {
        if (phi[i] == i) {                // ① i 是素数
            for (int j = i; j <= N; j += i) {
                phi[j] = phi[j] / i * (i - 1);
                // ② 对每个 i 的倍数，乘 (i-1)/i
            }
        }
    }
}

• ① 如果 phi[i] == i，说明 $i$ 还没被任何素数处理过，即 $i$ 是素数。
• ② 对 $i$ 的每个倍数 $j$，把 phi[j] 乘上 $(i-1)/i$。这对应公式 $\varphi(N) = N \prod_{p|N} \frac{p-1}{p}$。

例题

例题 1：M&A 014 — Factorization（★1）

题目：对整数 $N$ 进行素因数分解，按从小到大的顺序输出所有素因子（重复的重复输出）。

数据范围：$2 \le N \le 10^{12}$

—— AtCoder M&A 014

思路：素因数分解是欧拉函数的基础。欧拉函数 $\varphi(N) = N \prod_{p|N}(1 - 1/p)$ 的计算需要先做素因数分解。

代码：

#include <cstdio>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    for (long long i = 2; i * i <= N; i++) {
        while (N % i == 0) {
            printf("%lld ", i);
            N /= i;
        }
    }
    if (N > 1) printf("%lld", N);
    printf("\n");
}

---

例题 2：Tessoku Book — A31 Divisors

题目：给定正整数 $N$，求 $N$ 的正约数个数。

数据范围：$1 \le N \le 10^{12}$

—— AtCoder Tessoku Book A31

思路：先素因数分解 $N = p_1^{e_1} \times p_2^{e_2} \times \cdots$，则约数个数 $d(N) = (e_1+1)(e_2+1) \cdots$。

代码：

#include <cstdio>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    long long ans = 1;
    long long temp = N;
    for (long long i = 2; i * i <= temp; i++) {
        int e = 0;
        while (temp % i == 0) {
            e++;
            temp /= i;
        }
        if (e > 0) ans *= (e + 1);  // ① 每个素因子的指数+1 相乘
    }
    if (temp > 1) ans *= 2;  // ② 剩下一个大于√N的素因子，指数为1

    printf("%lld\n", ans);
}

逐行解析：

• ① 如果 $N = p_1^{e_1} \times p_2^{e_2}$，则每个素因子可以选择 $0$ 到 $e_i$ 次，共 $e_i + 1$ 种选择。总约数个数 = 所有 $(e_i + 1)$ 的乘积。
• ② 如果最后 temp > 1，说明还有一个大于 $\sqrt{N}$ 的素因子，指数为 1，贡献 $1+1=2$。

---

例题 3：欧拉函数的计算公式（理论推导）

题目：给定 $N$，用欧拉函数公式 $\varphi(N) = N \prod_{p|N}(1 - 1/p)$ 计算 $\varphi(N)$。

数据范围：$2 \le N \le 10^{12}$

思路：先做素因数分解，对每个不同的素因子 $p$，把答案乘以 $(1 - 1/p) = (p-1)/p$。为了避免浮点数，用整数运算：$\varphi(N) = N \times \prod_{p|N} \frac{p-1}{p}$。

代码：

#include <cstdio>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    long long ans = N;
    long long temp = N;
    for (long long i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            ans = ans / i * (i - 1);  // ① 乘以 (i-1)/i
            while (temp % i == 0)
                temp /= i;            // ② 除尽所有 i
        }
    }
    if (temp > 1)
        ans = ans / temp * (temp - 1);  // ③ 最后一个素因子

    printf("%lld\n", ans);
}

逐行解析：

• ① ans / i * (i - 1)：先除后乘防溢出。ans 一定是 i 的倍数（因为 $i|N$ 且初始 ans = N），所以整数除法不会丢精度。
• ② 对每个素因子只处理一次（除尽后 temp 不再包含 i）。
• ③ 和 ① 一样，处理最后一个大于 $\sqrt{N}$ 的素因子。

验证：$N = 12 = 2^2 \times 3$。$\varphi(12) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$。实际 $\varphi(12) = |\{1, 5, 7, 11\}| = 4$。✓

---

例题 4：T90 038 — Large LCM（★3）

题目：给定两个正整数 $A, B$，求 $\text{lcm}(A, B) \bmod (10^{18}+9)$（或判断是否超过 $10^{18}$）。

数据范围：$1 \le A, B \le 10^{18}$

—— AtCoder T90 038

思路：$\text{lcm}(A,B) = A / \gcd(A,B) \times B$。但 $A, B \le 10^{18}$，乘积可能超过 long long 范围。需要先检查是否溢出：如果 $A / \gcd(A,B) > 10^{18} / B$，则 LCM 超过 $10^{18}$。

代码：

#include <cstdio>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

int main() {
    long long A, B;
    scanf("%lld%lld", &A, &B);

    long long g = gcd(A, B);
    A /= g;

    if (A > 1000000000000000000LL / B)  // ① 检查 A/g * B 是否溢出
        printf("Large\n");
    else
        printf("%lld\n", A * B);
}

逐行解析：

• ① A > 10^{18} / B 等价于 $A \times B > 10^{18}$，但不用乘法（避免溢出），改用除法判断。

---

例题 5：M&A 042 — Sum of Divisors（★2）

题目：设 $f(X)$ 为 $X$ 的正约数个数。求 $\sum_{K=1}^{N} K \times f(K)$。

数据范围：$1 \le N \le 10^7$

—— AtCoder M&A 042

思路：和 02-03 例题 5 一样。这道题同时出现在多个章节——从”欧拉函数/约数”角度，它考察的是约数函数 $d(n)$ 的求和。

代码：（见 02-03 例题 5）

从欧拉函数的角度看，$\sum_{K=1}^{N} f(K)$ 就是 $\sum_{d=1}^{N} \lfloor N/d \rfloor$——枚举每个约数，统计它作为多少个数的约数出现。这种”转换视角”（从”每个数的约数”变成”每个约数对应的数”）是数论中的核心技巧。

参考文献

理论讲义 — AtCoder Algorithm Lectures

• Euclid の互除法（難易度 2）

教材讲解 — 競技プログラミングの鉄則 第 5 章

• 5.2 B27 Calculate LCM（GCD/LCM 解说）
• 欧拉函数为课堂延伸内容，教材本体 5.8 节涉及
• 素数の性質（難易度 3）

基础练习 — アルゴリズムと数学 演習問題集

• 014 Factorization（素因数分解）【例题】
• 042 Sum of Divisors（约数函数求和）【例题】
• 013 Divisor Enumeration（约数枚举）
• 015 Calculate GCD（GCD计算）
• 017 Least Common Multiple of N Integers

系统练习 — 競技プログラミングの鉄則

• A31 Divisors（约数个数）【例题】

实战练习 — 競プロ典型 90 問

• 038 Large LCM（★3，LCM与GCD）【例题】
• 077 Distance Sum（★3，排序+前缀和）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化