欧拉函数基础

欧拉函数的定义

欧拉函数（Euler's totient function），即 \(\varphi(n)\)，表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。

比如说 \(\varphi(1) = 1\)。

当 n 是质数的时候，显然有 \(\varphi(n) = n - 1\)。

---

欧拉函数的性质

• 欧拉函数是积性函数。

  积性是什么意思呢？如果有 \(\gcd(a, b) = 1\)，那么 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)。

  特别地，当 \(n\) 是奇数时 \(\varphi(2n) = \varphi(n)\)。

• \(n = \sum_{d \mid n}{\varphi(d)}\)。

  利用 莫比乌斯反演 相关知识可以得出。

  也可以这样考虑：如果 \(\gcd(k, n) = d\)，那么 \(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )\)。

  如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数，那么 \(n = \sum_{i = 1}^n{f(i)}\)。

  根据上面的证明，我们发现，\(f(x) = \varphi(\dfrac{n}{x})\)，从而 \(n = \sum_{d \mid n}\varphi(\dfrac{n}{d})\)。注意到约数 \(d\) 和 \(\dfrac{n}{d}\) 具有对称性，所以上式化为 \(n = \sum_{d \mid n}\varphi(d)\)。

• 若 \(n = p^k\)，其中 \(p\) 是质数，那么 \(\varphi(n) = p^k - p^{k - 1}\)。 （根据定义可知）

• 由唯一分解定理，设 \(n = \prod_{i=1}^{s}p_i^{k_i}\)，其中 \(p_i\) 是质数，有 \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\)。

  证明：

  • 引理：设 \(p\) 为任意质数，那么 \(\varphi(p^k)=p^{k-1}\times(p-1)\)。

    证明：显然对于从 1 到 \(p^k\) 的所有数中，除了 \(p^{k-1}\) 个 \(p\) 的倍数以外其它数都与 \(p^k\) 互素，故 \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)\)，证毕。

  接下来我们证明 \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\)。由唯一分解定理与 \(\varphi(x)\) 函数的积性

  \[ \begin{aligned} \varphi(n) &= \prod_{i=1}^{s} \varphi(p_i^{k_i}) \\ &= \prod_{i=1}^{s} (p_i-1)\times {p_i}^{k_i-1}\\ &=\prod_{i=1}^{s} {p_i}^{k_i} \times(1 - \frac{1}{p_i})\\ &=n~ \prod_{i=1}^{s} (1- \frac{1}{p_i}) \end{aligned} \]

---

求欧拉函数

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

    return res;
}

筛法求欧拉函数

\(1\)~\(N\)中与 \(N\) 互质的数的个数被称为欧拉函数，记为\(ϕ(N)\)。

若在算数基本定理中，\(N=p_1^{α1}p_2^{α2}···p_k^{αk}\)，则：

\(ϕ(N)=N∗\frac{p1−1}{p1}∗\frac{p2−1}{p2}∗…∗\frac{pk−1}{pk}\)

• 质数i的欧拉函数即为phi[i] = i - 1。
• phi[primes[j] * i]分为两种情况：
  1. i % primes[j] == 0：primes[j]是 i 的最小质因子，也是primes[j] * i的最小质因子，因此1 - 1 / primes[j]这一项在phi[i]中计算过了，只需将基数N修正为primes[j]倍，最终结果为phi[i] * primes[j]。
  2. i % primes[j] != 0：primes[j]不是 i 的质因子，只是primes[j] * i的最小质因子，因此不仅需要将基数N修正为primes[j]倍，还需要补上1 - 1 / primes[j]这一项，因此最终结果phi[i] * (primes[j] - 1)。

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉

void get_eulers(int n) {
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ) {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0) {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}