欧拉函数

概念讲解

什么是欧拉函数？

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

性质

  1. φ(1) = 1
  2. φ(p) = p - 1（p 是质数）
  3. φ(p^k) = p^k - p^(k-1)
  4. φ(nm) = φ(n)φ(m)（n, m 互质）

计算方法

单个数的欧拉函数

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

线性筛求欧拉函数

1234567891011121314151617181920212223242526const int N = 1000005;
int phi[N];
int primes[N], cnt;
bool isPrime[N];

void eulerSieve(int n) {
    phi[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = true;
            
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            } else {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

欧拉定理

定理

如果 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。

应用

求逆元：a 的逆元是 a^(φ(n)-1)。

考点分析

初赛考查方式

  1. 选择题： 欧拉函数的概念
  2. 程序阅读： 理解欧拉函数计算
  3. 编程题： 欧拉函数应用

常见题型

  • 欧拉函数计算
  • 互质数计数
  • 欧拉定理应用

例题精讲

例题 1：欧拉函数

题目： 求 φ(n)。

解答：

123456789101112131415161718192021222324252627282930#include <iostream>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    
    cout << euler(n) << endl;
    
    return 0;
}

练习题

  1. 洛谷 P2158 仪仗队
查看答案

思路：欧拉函数，求与 n 互质的数的个数。

123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    long long ans = 0;
    for (int i = 2; i < n; i++) {
        ans += euler(i);
    }
    
    cout << ans * 2 + 3 << endl;
    return 0;
}
  1. 洛谷 P2568 GCD
查看答案

思路：欧拉函数 + 前缀和。

123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream>
using namespace std;

const int N = 10000005;
int phi[N], prime[N], cnt;
bool isPrime[N];

void init() {
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!isPrime[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            isPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

int main() {
    init();
    
    int n;
    cin >> n;
    
    long long prefix[n + 1];
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + phi[i];
    }
    
    long long ans = 0;
    for (int d = 1; d <= n; d++) {
        ans += 2 * prefix[n / d] - 1;
    }
    
    cout << ans << endl;
    return 0;
}
  1. 洛谷 P1390 公约数的和
查看答案

思路：欧拉函数 + 前缀和。

12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>
using namespace std;

const int N = 2000005;
int phi[N], prime[N], cnt;
bool isPrime[N];

void init() {
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!isPrime[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            isPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

int main() {
    init();
    
    int n;
    cin >> n;
    
    long long ans = 0;
    for (int d = 1; d <= n; d++) {
        long long sum = 0;
        for (int i = d; i <= n; i += d) {
            sum += phi[i / d];
        }
        ans += d * sum;
    }
    
    cout << ans << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. 欧拉函数是积性函数
  2. 欧拉定理要求 gcd(a, n) = 1
  3. 线性筛可以同时求欧拉函数
  4. 欧拉函数与逆元有关