Preface

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

欧拉函数

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

性质

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

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

  1. φ(1)=1\varphi(1) = 1
  2. φ(p)=p−1\varphi(p) = p - 1 （pp 为质数）
  3. φ(pk)=pk−pk−1\varphi(p^k) = p^k - p^{k - 1} （pp 为质数）
  4. φ(m×n)=φ(m)×φ(n)\varphi(m \times n) = \varphi(m) \times \varphi(n) （mm 和 nn 互质）
  5. φ(n)=n×∏p∣n(1−1p)=n×∏p∣np−1p\varphi(n) = n \times \prod_{p|n} (1 - \frac{1}{p}) = n \times \prod_{p|n} \frac{p - 1}{p} （pp 为 nn 的质因数）
  6. φ(n)=φ(np)×(p−[np∤p])\varphi(n) = \varphi(\frac{n}{p}) \times (p - [\frac{n}{p} \nmid p]) （pp 为 nn 的最小质因数）

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

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

求法

根号单个求法

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

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

1
2
3
4
5
6
7
8
9
10
11
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)O(n) 的时间复杂度内求得 11 到 nn 的所有欧拉函数值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
        }
    }
}