欧拉函数学习笔记

Preface

复习数论的时候发现原来好像原来学过的全忘了，于是重新学习了一下，并记录如下。

欧拉函数

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

性质

欧拉函数是一个积性函数，即对于互质的两个数 $m$ 和 $n$，有 $\varphi(m \times n) = \varphi(m) \times \varphi(n)$，容易通过唯一分解定理证明。

这给我们提供了很多很好的性质。

1. $\varphi(1) = 1$
2. $\varphi(p) = p - 1$ （$p$ 为质数）
3. $\varphi(p^k) = p^k - p^{k - 1}$ （$p$ 为质数）
4. $\varphi(m \times n) = \varphi(m) \times \varphi(n)$ （$m$ 和 $n$ 互质）
5. $\varphi(n) = n \times \prod_{p|n} (1 - \frac{1}{p}) = n \times \prod_{p|n} \frac{p - 1}{p}$ （$p$ 为 $n$ 的质因数）
6. $\varphi(n) = \varphi(\frac{n}{p}) \times (p - [\frac{n}{p} \nmid p])$ （$p$ 为 $n$ 的最小质因数）

还有一个莫反得到的结论是 $\sum_{d|n} \varphi(d) = n$，因为没学过，暂时不知道怎么证明。

其中第三条性质可以通过定义证明：小于等于 $p^k$ 的数有 $p^k$ 个，其中有 $\frac{p^k}{p} = p^{k - 1}$ 个数是 $p$ 的倍数，所以有 $p^k - p^{k - 1}$ 个数与 $p$ 互质。

求法

根号单个求法

枚举 $n$ 的所有质因数 $p$，然后根据直接公式 $\varphi(n) = n \times \prod_{p|n} (\frac{p - 1}{p})$ 求得，时间复杂度为 $O(\sqrt{n})$。

值得一提的是，可以使用 Pollard-$\rho$ 算法来分解质因数，就能将时间复杂度降低到分解质因数的复杂度，约为 $O(\sqrt{p})$，其中 $p$ 为 $n$ 的最小质因数。（如果是大质数，可以用 Miller-Rabin 算法来判断）

int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

线性筛求法

利用线性筛和递推的思想，可以在 $O(n)$ 的时间复杂度内求得 $1$ 到 $n$ 的所有欧拉函数值。

std::vector<int> primes, min_p, phi;
std::vector<bool> is_prime;
void sieve(int n) {
    is_prime.resize(n + 1, true);
    min_p.resize(n + 1);
    phi.resize(n + 1);
    phi[1] = 1;
    is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            min_p[i] = i;
            phi[i] = i - 1;
        }
        for (auto p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            min_p[i * p] = p;
            phi[i * p] = phi[i] * (i % p ? p - 1 : p);
            if (i % p == 0) break;
        }
    }
}