欧拉函数

欧拉函数是什么

定义 欧拉函数 \varphi(n) 表示从 1 到 n 中与 n 互质的数的个数

若在算数基本定理中 N=p_1 ^ {c_1}p_2 ^ {c_2}...p_m ^ {c_m} , 则有:

等同于

证明

设 p 为 N 的质因子, 那么1到N中p的倍数有 p, 2p, 3p, ..., (N/p) * p, 一共有 N/p 个
同理, 我们设 q 也为 N 的另一个质因子, 那么 1 到 N 中为 q 的倍数有 N/q 个

那么如果我们将 N/p + N/q 个数字去掉就会发现同时为 p 和 q 的倍数的数字被去除了两次, 要加回来一次

然后我们就会得出如下式子:

其实就是运用了容斥原理
同样的, 我们可以用这个方式去除其他质因子的倍数, 得到的就是 1 到 N 中与 N 互质的数的个数, 最终推得上面的式子

证毕.

性质

积性函数

定义: 若a, b互质, 有 f(a)*f(b) = f(ab) , 那么就称 f 为积性函数

欧拉函数就是一个积性函数

那么欧拉函数就拥有了积性函数的性质, 即

1. \varphi(ab) = \varphi(a)*\varphi(b)
2. 当有 n = \prod_{i = 1} ^ {m} p_i ^ {c _ i}, 则 \varphi(n) = \prod_ {i = 1} ^ {m} \varphi(p_i ^ {c_ i})

证明(1)

《算法竞赛进阶指南》上只有一句话:

根据欧拉函数的计算式, 对 a, b 进行分解质因数, 直接可得性质2. 把性质2推广到一般的函数上, 可以得到 "积性函数" 的概念.
证毕.

额, 怎么不算证明呢

本人时间有限实际就是懒得写, 读者可以自己根据这个证明一下, 这里不再进行其他说明

证明(2)

对n分解质因数, 再结合积性函数的定义, 显然性质2成立.
证毕.

其他说明我觉得不太必要了, 有需要可以自己算算

欧拉函数的性质

1. 上面有了
2. 同上
3. \forall n > 1 , 1 到 n 中与 n 互质的数字和为 n * \varphi(n)/2
4. 若 n 为质数, 有\varphi(n) = n - 1
5. 若 n 为质数, 有 \varphi(n ^ k) = (n - 1) * n ^{k - 1} = n ^ k - n ^{k - 1}
6. 若 p 为质数, 若 p\mid n 但是 p ^ 2 \mid n , 则 \varphi(n) = \varphi(n/p) * p
7. 若 p 为质数, 若 p\mid n 但是 p ^ 2 \nmid n , 则 \varphi(n) = \varphi(n/p) * (p - 1)
8. \sum _ {d \mid n} \varphi(d) = n

证明（3 ~ 6）

1. 略
2. 略
3. 因为 gcd(n, x) = gcd(n, n - x) , 所以我们发现与
   n 不互质的两个数 x, n - x 总是成对出现, 平均值 n / 2 , 得证.
4. 显然
5. 其实就是定义式的变形, 可以自己带个数算算, 也挺显然的
6. 若 p 为质数, p\mid n 但是 p ^ 2 \mid n , 则有n, n/p 包含相同的质因子, 因为积性函数, 只是 p 的指数不同. 直接写 \varphi (n) 与 \varphi (n/p) 的公式, 两者相除得 p , 得证.
7. 若 p 为质数, 若 p\mid n 但是 p ^ 2 \nmid n , 说明 p, n/p 互质, 由积性函数得 \varphi(n) = \varphi(n/p) * \varphi(p) , 又有 \varphi(p) = p - 1 , 得证.
8. 设 f(n) = \sum _{d \mid n} \varphi(d) .
   由乘法分配律和积性函数, 易得 f(nm) = \sum _ {d \mid nm} \varphi(d) = (\,\sum_ {d \mid n} \varphi(d)\,) * (\,\sum _{d \mid m} \varphi(d)\,) = f(n) * f(m).
   现在我们知道了我们设的函数为一个积性函数.
   那么对于单个质因子有 f(p ^ m) = \sum _ {d \mid p ^ m} = \varphi(1) + \varphi(p) + \varphi(p ^ 2) + ... + \varphi(p ^ {m - 1}), 相当于一个等比函数再加一, 最终为 p ^ m .
   那么就有 f(n) = \prod _ {i = 1} ^ {m} f(p_i ^{c_i}) = \prod _ {i = 1} ^ {m} p_i ^ {c _ i} = n .
   证毕.

求欧拉函数

累死了终于不用到处证明了

试除法

都试除法了, 那肯定是使用的唯一分解定理啦

我们直接把之前推过的式子搬下来

显然, 上面的式子等同于:

p \mid N 表示的就是N的质因子

欧拉函数仅由 n 与质因子决定, 与次数无关

分解质因数的复杂度为 O(\sqrt n) , 计算欧拉函数的复杂度为 O(\sqrt n) , 若要求 2 ~ n 的欧拉函数的话就是 O(n \sqrt n)

int phi(int n) { //试除法求欧拉函数(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;
}

埃氏筛

同样使用欧拉函数的计算公式

求出 2 ~ n 的欧拉函数的时间复杂度为 O(n \sqrt n)

void varphii(int n) { //埃氏筛求欧拉函数(2 ~ n)
    for (int i = 2; i <= n; i++) phi[i] = i;

    for (int i = 2; i <= n; i++) 
        if (phi[i] == i)
            for (int j = i; j <= n; j += i)
                phi[j] = phi[j] / i * (i - 1);
}

线性筛

用以上两种算法已经能解决大部分求欧拉函数的问题

但是有没有一种算法能优化时间复杂度呢?

有的兄弟, 有的

用线性筛的思想就能将求出 2 ~ n 的欧拉函数的时间复杂度降到 O(n)

在线性筛中, 每个数都只会被自己的最小的质因子筛掉
结合我们之前列出的性质6与性质7

6. 若 p 为质数, 若 p\mid n 但是 p ^ 2 \mid n , 则 \varphi(n) = \varphi(n/p) * p
7. 若 p 为质数, 若 p\mid n 但是 p ^ 2 \nmid n , 则 \varphi(n) = \varphi(n/p) * (p - 1)

我们就可以用 \varphi(n / p) 推出 \varphi(n)

然后就是你们最喜欢的代码环节

int phi[MN], vis[MN], p[MN], cnt;
//欧拉函数; 访问标记(未标记的为质数); 质数; 质数计数器

void varphi(int n){ //线性筛求欧拉函数(1 ~ n)
    phi[1] = 1;
    for (int i = 2; i <= n; i++){
        if (vis[i] == 0){
            p[++cnt] = i; //下标从1开始!! 
            phi[i] = i - 1; //若为质数则减一 
        }

        for (int j = 1; j <= cnt; j++){
            if (i * p[j] > n) break;

            int m = i * p[j];
            vis[m] = 1; //非质数标记 
            if (i % p[j] == 0){ //i能被p[j]整除则i包含了m的所有质因子 
                phi[m] = phi[i] * p[j];
                break;
            }
            else { //不能整除说明互质 
                phi[m] = phi[i] * (p[j] - 1); //注: phi[j] = p[j] - 1
            }
        }
    }
}

例题

洛谷P2158 仪仗队

题目描述

作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 N \times N 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

输入格式

一行，一个正整数 N。

输出格式

输出一行一个数，即 C 君应看到的学生人数。

输入输出样例 #1

输入 #1

4

输出 #1

9

说明/提示

对于 100 \% 的数据，1 \le N \le 40000。

解题思路

我们仔细观察上图, 注意到若一个学生能被看到, 那么他所站的位置距离C君的水平距离 (x) 和竖直距离 (y) 满足 gcd(x, y) = 1

那么 当 n > 2 时 n 每增大 1 , 在同一行或同一列上新的能看到的学生数量就是与 n - 1 互质的学生数量, 即 \varphi (n - 1) , 可以自己列一下感受一下

我们还发现像这样的学生总是成对出现, 结合打表 (我认真的) , 很容易就能得出这样的式子 (我这里设了个函数 f 表示答案) :

然后...上代码吧

代码

#include <bits/stdc++.h>
using namespace std;

const int MN = 40003;
int n, ans = 1;
int phi[MN], vis[MN], p[MN], cnt; 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    phi[1] = 1;
    for (int i = 2; i < n; i++){
        if (vis[i] == 0){
            p[++cnt] = i;
            phi[i] = i - 1;
        }

        for (int j = 1; j <= cnt; j++){
            if (i * p[j] > n) break;

            int m = i * p[j];
            vis[m] = 1;
            if (i % p[j] == 0){
                phi[m] = phi[i] * p[j];
                break;
            }
            else {
                phi[m] = phi[i] * (p[j] - 1);
            }
        }
    }

    for (int i = 1; i < n; i++) ans += phi[i] * 2;

    cout << ans;

    return 0;
}

内容参考《算法竞赛进阶指南》与上课的课件