欧拉函数

joeylu1001 · 2024-04-03 00:53:58 · 算法·理论

定义

对于任意正整数 n，定义欧拉函数 \varphi(n) 为小于等于 n 且与 n 互质的正整数的个数，即

\varphi(n) = \sum _ {i = 1} ^ {n} [n \perp i].

性质

积性：当且仅当正整数 a, b 满足 a \perp b 时，有 \varphi(ab) = \varphi(a) \cdot \varphi(b)。

此处只证明充分性，即 a \perp b \Rightarrow \varphi(ab) = \varphi(a) \cdot \varphi(b)。

证明：设小于等于 a 且与 a 互质的正整数为 x_1, x_2, \cdots, x_{\varphi(a)}，小于等于 b 且与 b 互质的正整数为 y_1, y_2, \cdots, y_{\varphi(b)}，小于等于 ab 且与 ab 互质的正整数为 z_1, z_2, \cdots, z_{\varphi(ab)}。

对于关于 t 的同余方程组 \begin{cases} t \equiv x_i \pmod a, \\ t \equiv y_j \pmod b, \end{cases} 由中国剩余定理知在模 ab 意义下有且仅有一组解。又因为 x_i \perp a, y_j \perp b，所以 t \perp a, t \perp b，t \perp ab，t 即是某个 z。故对于任意 (x_i, y_j) 存在一个 z_k 与之对应。

对于 z_k 满足 z_k \perp ab，则 z_k \perp a, z_k \perp b，所以 z_k \bmod a \perp a, z_k \bmod b \perp b，z_k \bmod a 即是某个 x，z_k \bmod b 即是某个 y。故对于任意 z_k 都存在一组 (x_i, y_j) 与之对应。

综上，对于任意 (x_i, y_j) 存在唯一一个 z_k 与之对应。所以 \varphi(ab) = \varphi(a) \cdot \varphi(b)。
反演：n = \sum _ {d \mid n} \varphi(d)。

证明：对于任意正整数 x，定义 f(x) 为满足 \gcd(n, i) = x 且 i \le n 的正整数 i 的个数，即 f(x) = \sum _ {i = 1} ^ n [\gcd(n, i) = x]。则有 n = \sum _ {i = 1} ^ {n} f(i)。

易证若 x \nmid n 则有 f(x) = 0，所以 n = \sum _ {d \mid n} f(d)。
所以 $n = \sum _ {d \mid n} \varphi(\frac{n}{d})$。注意到 $n$ 的因数 $d$ 与 $\frac{n}{d}$ 具有对称性，因此 $n = \sum _ {d \mid n} \varphi(d)$。
对于任意质数 p，有 \varphi(p ^ k) = p ^ k - p ^ {k - 1}。

证明：1 \sim p ^ k 这 p ^ k 个数中，不与 p _ k 互质的数只有 p 的倍数，即 p, 2p, 3p, \cdots, p ^ {k - 1} \cdot p 共 p ^ {k - 1} 个。所以 \varphi(p ^ k) = p ^ k - p ^ {k - 1}。
对于正整数 x，由唯一分解定理，设 x = \prod _ {i = 1} ^ s p _ i ^ {k _ i}，其中 p 为质数。则 \varphi(x) = x \cdot \prod _ {i = 1} ^ s (1 - \frac{1}{p_i})。

证明：

\begin{aligned} \varphi(x) &= \varphi(\prod _ {i = 1} ^ s p _ i ^ {k _ i}) \\ &= \prod _ {i = 1} ^ s \varphi(p _ i ^ {k _ i}) \\ &= \prod _ {i = 1} ^ s p _ i ^ {k _ i} - p ^ {k _ i - 1} \\ &= \prod _ {i = 1} ^ s p _ i ^ {k _ i} \cdot(1 - \frac{1}{p _ i}) \\ &= x \cdot \prod _ {i = 1} ^ s 1 - \frac{1}{p_i} \end{aligned}

推论：\varphi(ab) = \varphi(a) \cdot \varphi(b) \Rightarrow a \perp b。

显然当 a, b 有公共质因子时 \varphi(ab) > \varphi(a) \cdot \varphi(b)。至此我们证明了欧拉函数的积性。

实现

O(\sqrt{n}) 求解 \varphi(n)

因为 \varphi(x) = x \cdot \prod _ {i = 1} ^ s (1 - \frac{1}{p_i})，所以我们可以在 O(\sqrt{n}) 的时间内将 n 分解质因数，求出 \varphi(n)。

int phi(int n)
{
    int res = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) // i 是 n 的质因子
        {
            res = res / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    if (n != 1)
        res = res / n * (n - 1);
    return res;
}

O(n) 求解 \varphi(1), \varphi(2), \cdots, \varphi(n)

对于任意 i \le n，线性筛可以 O(n) 求出 i 的最小质因子 p_i，考察 \varphi(i) 与 p_i 的关系：

若 i = p_i，即 i 是质数，则由性质 3 得 \varphi(i) = i - 1。
若 p_i \perp \frac{i}{p_i}，则由性质 2、3 得 \varphi(i) = \varphi(p _ i) \cdot \varphi(\frac{i}{p_i}) = (p _ i - 1) \cdot \varphi(\frac{i}{p_i})。
若 p_i, \frac{i}{p_i} 不互质，则 \varphi(i) = p _ i \cdot \varphi(\frac{i}{p_i})。

证明：若 p_i, \frac{i}{p_i} 不互质，则一定有 p_i 是 \frac{i}{p_i} 的质因子。

设 i = p ^ k q，其中 p \perp q，则有
\begin{aligned} \varphi(i) &= \varphi(p ^ k q) \\ &= \varphi(p ^ k) \cdot \varphi(q) \\ &= (p ^ k - p ^ {k - 1}) \cdot \varphi(q) \\ &= p \cdot \varphi(p ^ {k - 1}) \cdot \varphi(q) \\ &= p \cdot \varphi(p ^ {k - 1} \cdot q) \\ &= p \cdot \varphi(\frac{i}{p_i}). \end{aligned}

所以我们可以在线性筛的基础上求解欧拉函数。

phi[1] = 1;
for (int i = 2; i <= n; i++)
{
    if (phi[i] == 0)
    {
        p[++p[0]] = i;
        phi[i] = i - 1;
    }
    for (int j = 1; j <= p[0] && i * p[j] <= n; j++)
        if (i % p[j] == 0)
        {
            phi[i * p[j]] = p[j] * phi[i];
            break;
        }
        else
            phi[i * p[j]] = (p[j] - 1) * phi[i];
}