当前位置：首页 > news >正文

欧拉函数总结

news 2026/5/12 2:02:01

定义

$\varphi(n)$ 表示小于等于 $n$ 的正整数中与 $n$ 互质的数的个数.

性质 1

若 $p$ 为质数，则 $\varphi(p^k) = p^k - p^{k - 1}$.

证明：
考虑容斥，令 $n = p^k$ 用 $n$ 减去 $n$ 以内所有不与 $n$ 互质的数.
由于 $n$ 只有 $p$ 这一个质因子，所以所有与 $n$ 不互质的数就是 $p$ 的倍数.
则 $\varphi(n) = n - \frac{n}{p} = p ^ k - p ^ {k - 1}$.

性质 2

若 $a \mid n$，则 $\varphi(an) = \varphi(n) \times a$.

证明 1：

\[\varphi(an) = an \times \prod_{i = 1}^{k} \frac{p_i - 1}{p_i} \]

因为 $an$ 和 $n$ 的质因子集合相同，所以.

\[\varphi(an) = a \times \varphi(n) \]

证明 2：
对于一个数 $x$，由辗转相除知，有 $\gcd(x, n) = \gcd(x + m, n)$.
若 $x$ 与 $n$ 互质，则 $\gcd(x, n) = \gcd(x + kn, n) = 1$，由于 $a \mid n$ 所以 $\gcd(x + kn, an) = 1$.
若 $x$ 与 $n$ 不互质，则 $\gcd(x, n) = \gcd(x + kn, n) > 1$，由于 $a \mid n$ 所以 $\gcd(x + kn, an) > \gcd(x + kn, n) > 1$.

性质 3

若 $m$ 与 $n$ 互质，$\varphi(mn) = \varphi(m) \times \varphi(n)$。
不可证。

计算

方法 1 直接计算单个

\[n = \prod_{i = 1}^k p_i^{t_i} \]

由性质 3 知

\[\varphi(n) = \prod_{i = 1}^k \varphi(p_i^{t_i}) \]

由性质 1 知

\[\varphi(p_i^{t_i}) = p_i^{t_i} - p_i^{t_i - 1} \]

则

\[\varphi(n) = n\prod_{i = 1}^k \frac{p_i - 1}{p_i} \]

时间：$O(\sqrt n)$

方法 2 线性筛欧拉函数求 $n <= m$ 的逆元

初始状态：$phi_1 = 1$
过程：

$n$ 是质数 $phi_i = i - 1$（性质 1）
$n$ 是合数 $p \times i$
a. $p \mid i$，则 $phi_{p \times i} = phi_{i} \times p$（性质 2）
b. 否则，$phi_{p \times i} = phi_p \times phi_i$（性质 3）

要点

先除后乘，以免爆 long long
龟速乘

Problem

UVA10179 Irreducable Basic Fractions

UVA11327 Enumerating Rational Numbers

P1891 疯狂 LCM

题解

推式子.

\[\sum\limits_{i = 1}^n \operatorname{lcm}(i, n) \]

根据 $\operatorname{lcm}$ 的定义变换.

\[\sum\limits_{i = 1}^n \frac{i \times n}{\gcd(i, n)} \]

考虑枚举 $\gcd$，为互质和欧拉函数作铺垫.

\[n\sum\limits_{i = 1}^n \sum\limits_{d \mid n} [\gcd(i, n) = d] \times \frac{i}{d} \]

$\gcd$ 内外可以同时除，转化为互质.

\[n\sum\limits_{i = 1}^n \sum\limits_{d \mid n} [\gcd(\frac{i}{d}, \frac{n}{d}) = 1] \times \frac{i}{d} \]

换元简洁形式.

\[n\sum\limits_{d \mid n} \sum\limits_{i = 1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1] \times i \]

上式为互质数和的形式。有一个式子，当 $n > 1$ 时，有$\sum\limits_{\{x\mid 1 \le x \le n,x \perp n\}} x = 2n\varphi(n)$.

证明：
对于一个 $x$，有 $1 = \gcd(x, n) = \gcd(-x, n) = \gcd(n - x, n)$，则 $x$ 是成对出现且每对和为 $n$ 的，由此得。因为当 $n = 1$ 时，$\varphi(n) = 1,x = 1$，所以直接用就行。

\[n + n\sum\limits_{d \mid n,d \not = n} \frac{2n\varphi(\frac{n}{d})}{d} \]

\[n + n\sum\limits_{d \mid n,d \not = 1} 2d\varphi(d) \]

启示

当 $n > 1$ 时，有$\sum\limits_{\{x\mid 1 \le x \le n,x \perp n\}} x = 2n\varphi(n)$.
由 $\gcd$ 到互质再到欧拉函数.

P3601 签到题

题解

由于每个数最多只有一个质因子是大于 $\sqrt n$ 的且要么 $n$ 为质数，要么 $n$ 的最小质因子小于 $\sqrt n$，所以考虑求出 $< \sqrt n$ 的所有质数。此时，若使用欧拉筛线性求，则需要 $ < n$ 的所有数的函数值，但这不可能。所以考虑直接求，直接求需要分解质因数，由于区间是连续的，所以考虑对每一个质数，枚举其在区间中的所有倍数，这样就可以大大降低分解质因数的时间复杂度。