> For the complete documentation index, see [llms.txt](https://wandersofb.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wandersofb.gitbook.io/blog/suan-fa/shu-xue/ou-la-han-shu.md).

# 欧拉函数

#### 欧拉函数

**互质**

在介绍欧拉函数之前，要先看一个概念-互质。互质是公约数只有 1 的的两个数。如果 $$a \equiv 1 \pmod b$$，那么 a 和 b 互质。 在约数那章已经说过了，算术基本定理为 $$N = p\_1^{a\_1}p\_2^{a\_2}\cdots p\_n^{a\_n}$$。好的，在知道了这两个概念后就可以介绍欧拉函数了。

**欧拉函数定义**

> $$1 \sim N$$ 中与 $$N$$ 互质的数的个数被称为欧拉函数，记为 $$\phi(N)$$。可表示为

$$
\phi(N) = N \* {p\_1 - 1 \over p\_1} \* {p\_2 - 1\over p\_2} \* \cdots \* {p\_m - 1\over p\_m}
$$

**如何求欧拉函数**

简单的分解质因数可以做到求解这个函数。也可以用线性筛的方法求解从 $$1 \sim N$$ 每个数的欧拉函数。

**分解质因数求欧拉函数**

分析这个函数，求出 $$N$$ 所有质数即可求出它的欧拉函数。

```cpp
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int eulor(int m){
    int res = m;
    for (int i = 2; i <= m / i; i ++){
        if (m % i == 0){
            while (m % i == 0)
                m /= i;
            res = res / i * (i - 1); // 先/后×，避免乘法溢出
        }
    }
    if ( m > 1) res = res / m * (m - 1);
    return res;
}

int main(){
    int n; cin >> n;
    while (n -- ){
        int m; cin >> m;
        cout << eulor(m) << endl;
    }
}
```

**时间复杂度分析**

和分解质因数一样，eulor 函数的时间复杂度为 $$O(\sqrt m)$$，总时间复杂度 $$O(n \sqrt m)$$。

**线性筛求欧拉函数**

线性筛不是求单个数的欧拉函数，它可以求出 $$1 \sim n$$ 中所有数的欧拉函数。 下面我们分析一下欧拉函数在线性增长的情况。

* 如果 $$i$$ 是质数，那么由公式可以看出从$$1 \sim i$$ 中为它互质的数 $$i-1$$。
* 如果 `i % p[j] != 0`，$$i$$ 是 $$i \* p\[j]$$ 的质因子，那么

$$
\ \phi(p\[j] \* i) = p\[j] \* i \* {q\_1 - 1\over q\_1} \* \cdots \* {q\_n - 1\over q\_n} \* {p\[j] - 1 \over p\[j]}
$$

* 如果 `i % p[j] == 0`，$$i$$ 不是 $$i \* p\[j]$$ 的质因子，那么

$$
\phi(p\[j] \* i) = p\[j] \* i \* {q\_1 - 1\over q\_1} \* \cdots \* {q\_n - 1\over q\_n}
$$

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int p[N], phi[N], cnt;
bool tou[N];

void eulor(int n){
    phi[1] = 1;
    for (int i = 2; i <= n; i ++){
        if (!tou[i]) {
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; p[j] <= n / i; j ++){
            tou[p[j] * i] = true;
            if (i % p[j] == 0){
                phi[i * p[j]] = p[j] * phi[i];        
                break;
            }
            phi[i * p[j]] = (p[j] - 1) * phi[i];
        }
    }  
}

int main(){
    int n; cin >> n;
    eulor(n);
    long long res = 0;
    for (int i = 1; i <= n; i ++)
        res += phi[i];
    cout << res;
}
```

**时间复杂度分析**

同线性筛一样 $$O(n)$$。

**欧拉函数总结**

欧拉函数是求互质的数的个数，至于具体的使用场景，等以后发现了补充。