本编介绍的是欧拉函数，其中欧拉筛打表欧拉函数是本章重点。

欧拉函数：

【互质】

        a 与 b 互质：说明 a 与 b 的最大公约数是 1.

【欧拉函数】

        对于一个数 n，在 1~n 中，与 n 互质的数的个数，就是欧拉函数，用表示。比如：。

【积性函数】

        若函数  满足：。则称其为积性函数。

【欧拉函数的性质】

1、若 p 为质数，则；

2、若 p 为质数，则；

3、欧拉函数为积性函数：。

【试除法求单个数的欧拉函数】

        计算公式：。

        推导过程：

由此可知，在求解某一个数的欧拉函数时，我们只需要知道它的质因数就可以求解。

// 试除法求解某一个数的欧拉函数，根据计算公式可得，其只与它的质因数有关，而且是分阶段的
int phi(int n)
{
    int ret = n;
    for (int i = 2; i <= x / i; i++)
    {
        if (n % i == 0) // 找到 i 的质因数
        {
            ret = ret / i * (i - 1); // 先除后乘，这是防溢出的写法
            while (n % i == 0) // 通过最小质因数除尽，之后就不会以 i的倍数 当作n的质因数了
            {
                n /= i;
            }
        }
    }
    
    // 特判此时如果有大于sqrt(n)的质因数
    if (n > 1) ret = ret / n * (n - 1);
    
    return ret;
}

时间复杂度：

        枚举到 sqrt(n)，因此时间复杂度为 O(sqrt(n))。

---

【欧拉筛打表欧拉函数】

        这其实就是用线性筛打表，在线性筛的过程中算出每个数对应的欧拉函数。

        问题背景：需要知道 [1，n] 中，每个数的欧拉函数。

📌在线性筛的过程中：

        1、如果是质数，则就用欧拉函数的性质一，i 的欧拉函数就是 i - 1；

        2、如果是合数：

                现令 x = i * p[j]：

                2.1、i % p[j] != 0：就代表 i 和 p[j] 是互质的，就可以用欧拉函数的性质三，x 的欧拉函数就是 （i 的欧拉函数）* （p[j] 的欧拉函数），p[j] 是质数，又可以用欧拉函数的性质一，p[j] - 1， 。

                2.2、i % p[j] == 0：就代表 p[j] 是 i 的因数，i 这个数里面包含了 x 所有的质因子，用公式计算，再用 i 和 x 的因子相同，等价交换：

int n;
bool st[N];
int p[N], cnt;
int phi[N]; // 欧拉函数表

void get_phi()
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            p[++cnt] = i;
            phi[i] = i - 1; // 性质一
        }

        for (int j = 1; 1ll * i * p[j] <= n; j++)
        {
            int x = i * p[j];
            st[i * p[j]] = true;

            if (i % p[j] != 0)
            {
                phi[x] = phi[i] * (p[j] - 1); // （主）性质三 + 性质一
            }
            else
            {
                phi[x] = p[j] * phi[i]; // 公式法 （正推拆 + 反推合）
                break;
            }
        }
    }
}

时间复杂度：

        时间复杂度与线性筛一致，O(n)。