欧拉函数

1.欧拉函数

  • 欧拉函数定义：1~n中与n互质的数的个数，例$φ(6) = 2$
  • 如果 $N = p1^{α1}p2^{α2}….*pn^{αn}$
  • 则有公式：$φ(N) = N*(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pn})$；
  • 时间复杂度：$O(n) = \sqrt{n}$

image-20230407220120947.png

2.AcWing873.欧拉函数

对于每一个数字，分别从定义出发求其欧拉函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;

int main() {
    int m; cin >> m;
    while (m--) {
        int num; cin >> num;
        int res = num;//最后结果
        //1.分解质因数
        for (int i = 2; i <= num / i; ++i) {
            if (num % i == 0) {
                /* i为num的一个因子 */    
                res = res / i * (i - 1);//res = res * (1 - 1/i);公式内容
                while (num % i == 0) num /= i;
            }
        }
        //2.说明num有一个大于1的质因数
        if (num > 1) res = res / num * (num - 1);
        cout << res << endl;
    }
    return 0;
}
  • 注意：在 res = res / num * (num - 1)中, 不能写成 res = res * (num - 1) / num;顺序不可颠倒

3.AcWing874.筛法求欧拉函数

如果需要求出1~N中，每一个数字的欧拉函数，这时再使用公式法（将每个数都分解质因数）将导致时间复杂度为$O(n) = n\sqrt{n}$

在筛法求素数的过程中，计算出每一个数的欧拉函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
using namespace std;

const int MAX = 1000010;

int primes[MAX], cnt;//质数数组、质数下标
bool st[MAX];//每个数字是否已经被筛选掉

int phi[MAX];

long long get_eulers(int n) {
    /* 线性筛法过程中 顺便将欧拉函数求一遍 */
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) {
            primes[cnt++] = i;//质数添加
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
            st[primes[j] * i] = true;//进行筛选
            if (i % primes[j] == 0) {//优化为线性的
                phi[primes[j] * i] = phi[i] * primes[j];//数学推导
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);//数学推导
        }
    }
    //计算总和
    long long res = 0;
    for (int i = 1; i <= n; ++i) res += phi[i];
    return res;
}

int main() {
    int n; cin >> n;
    cout << get_eulers(n) << endl;
    return 0;
}
  • 欧拉定理：若a与n互质，则有 $a^{φ(n)}≡1(mod~n)$
  • 费马定理：当n为质数时，则有 $a^{p-1}≡1(mod~p)$