欧拉函数的定义：

首先欧拉函数的记号是 $\phi$，$\phi(N)$ 表示 $1 \sim N$ 中和 $N$ 互质的数的个数，就比如 $\phi(6)$，$1$ 和 $5$ 与 $6$ 互质，其它数和 $6$ 不互质，所以 $\phi(6) = 2$。

欧拉函数的求法：

假如 $N$ 分解质因数是：
$$N = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}$$
那么 $\phi(N)$ 就是：
$$\phi(N) = N \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k}$$
也就是：
$$\phi(N) = N \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_k})$$

证明：

这个用到了容斥原理（后面会讲）。
由于 $p_1 \sim p_k$ 的所有倍数都肯定不是跟 $N$ 互质的，所以都去掉

第一步： 从 $1 \sim N$ 中，去掉 $p_1 \sim p_k$ 的所有倍数。
也就是：
$$ans \gets N - \frac{N}{p_1} - \frac{N}{p_2} - \cdots - \frac{N}{p_k}$$

但如果 $1 \sim N$ 中的一个数，它既是 $p_i$ 的倍数，也是 $p_j$ 的倍数，那他就会被减两次，这就不对了，我们就得给他加回来。

第二步： 从 $1 \sim N$ 中，加上 $\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}p_i \times p_j$ 的所有倍数。
也就是：
$$ans \gets ans + \frac{N}{p_1p_2} + \frac{N}{p_1p_3} + \cdots + \frac{N}{p_{k-1}p_k}$$

如果有的话，那么如果一个数是三个、四个、五个或更多质数的乘积，就还得减、加、减，最后，就是这样的：
$$\begin{aligned} ans \gets N &- \frac{N}{p_1} - \frac{N}{p_2} - \cdots - \frac{N}{p_k} \\ &+ \frac{N}{p_1p_2} + \frac{N}{p_1p_3} + \cdots \\ &- \frac{N}{p_1p_2p_3} - \cdots \\ &+ \frac{N}{p_1p_2p_3p_4} + \cdots \\ &- + - \vdots \end{aligned}$$

然后 $\phi(N)$ 就应该等于上面那一坨，经过展开最上面的式子也能得到这一坨，上面就是简化之后的。

代码：

int phi(int x){
    int daan = x;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0){
            daan = daan / i * (i - 1); // 细节
            while (x % i == 0) x /= i;
        }
    if (x > 1) daan = daan / x * (x - 1);
    return daan;
}

这段代码的时间复杂度瓶颈就在于分解因数，是 $O(n \sqrt n)$ 的时间复杂度。

欧拉函数的筛法：

解决的问题是这道题。

这次这是要求 $1 \sim n$ 中所有数的欧拉函数，就跟质数筛看起来差不多，所以直接 copy 代码（因为 $O(n \sqrt n)$ 的时间复杂度太慢了）。

void get_primes(){
    for (int i = 2; i <= n; i++){
        if (!st[i]) primes[++cnt] = i;
        for (int j = 1; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

我们需要先改一下函数名和添加一个 $\phi$ 数组 phi[N]：

int phi[N];
void get_eulers(){
    for (int i = 2; i <= n; i++){
        if (!st[i]) primes[++cnt] = i;
        for (int j = 1; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

函数类型没必要改，y 总只是把所有的代码都放在了一个函数里了而已，

如果一个数 $p$ 是质数，那么 $1 \sim p - 1$ 肯定都与他互质，那么 $\phi(p) = p - 1$。对了，$\phi(1)$ 就是 $1$，初始化也得加上。

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

再看剩下几种情况，如果第二层循环中，$i \bmod p_j = 0$，也就是说 $p_j$ 是 $i$ 的最小质因子，$i$ 分解质因数等于 $p_1^{\alpha_1} \times \cdots \times p_j^{\alpha_j} \times \cdots \times p_k^{\alpha_k}$，那么 $i \times p_j$ 分解质因数就是 $p_1^{\alpha_1} \times \cdots \times p_j^{\alpha_j + 1} \times \cdots \times p_k^{\alpha_k}$，由于欧拉函数中只跟底数有关系，跟次数没关系，所以 $\phi(i \times p_j)$ 后面乘的几分之几就跟 $\phi(i)$ 一样了，$\phi(i \times p_j)$ 就等于 $p_j \times i \times (\phi(i) \div i)$，后面括号里的部分就是 $\phi(i)$ 的几分之几部分，简化一下就是 $p_j \times \phi(i)$，非常神奇，$\phi(p_j \times i) = p_j \times \phi(i)$，就跟 DP 差不多。
但如果，$i \bmod p_j \neq 0$，也就是说 $p_j$ 小于 $i$ 的最小质因子，那无非就在 $\phi$ 后面几分之几的部分又乘了一个 $\frac{p_j - 1}{p_j}$，就是说 $\phi(p_j \times i) = p_j \times \frac{p_j - 1}{p_j} \times \phi(i)$，也就是 $(p_j - 1) \times \phi(i)$。

好，在代码里再加上这两种情况，就完成了。

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

最后 phi[i] 里存的就是 $i$ 的欧拉函数（话说这段代码还能顺便求一下质数），把他们加起来就行了。

欧拉定理：

欧拉定理在后面还会用。
若 $a$ 与 $n$ 互质，则 $a^{\phi(n)} \equiv 1 \pmod n$。

就比如 $a$ 是 $5$，$n$ 是 $6$，那么：
$$\begin{aligned} a^{\phi(n)} \bmod 6 &= 5^{\phi(6)} \bmod 6 \\ &= 5^2 \bmod 6 \\ &= 25 \bmod 6 \\ &\equiv 1 \end{aligned}$$

证明：

假如 $1 \sim n$ 中与 $n$ 互质的数是 $b_1, b_2, \ldots, b_{\phi(n)}(1 \sim n 中跟 n 互质的有 \phi(n) 个)$，那么 $a \cdot b_1, a \cdot b_2, \ldots, a \cdot b_{\phi(n)}$ 也都和 $n$ 互质，毕竟两个跟 $n$ 互质的数乘起来当然也跟 $n$ 互质。
我们把上面那一组数 $\bmod n$ 的值记作 $c_1 \sim c_{\phi(n)}$，这里面的值也都是和 $n$ 互质的，都证过了，然后这里面的值也都是两两不相同的，我们用反证法来证。
假如 $c_i = c_j$，就说明 $a \cdot b_i \equiv a \cdot b_j \pmod n$ 两边同时消掉 $a$ 就变成了 $b_i \equiv b_j \pmod n$，由于这与之前的设定不符，所以绝对不会成立，反证法成功。

由于只是顺序不同，数都一样，所以前面的乘起来就等于后面的乘起来，所以就是：
$$ a \cdot b_1 \cdot a \cdot b_2 \cdots a \cdot b_{\phi(n)} \equiv b_1 \cdots b_{\phi(n)} \pmod n $$
也就是：
$$ a^{\phi(n)} \cdot (b_1 \cdots b_{\phi(n)}) \equiv b_1 \cdots b_{\phi(n)} \pmod n $$
左右两边一消 $b_1 \cdots b_{\phi(n)}$，就变成最开始那个式子：
$$ a^{\phi(n)} \equiv 1 \pmod n $$

有个特殊情况，假如 $n$ 是质数（用 $p$ 来表示），那么这个式子就变成了：
$$ a^{p-1} \equiv 1 \pmod p $$
因为质数的欧拉函数就是它减一嘛，这个定理也被称为费马小定理，以后会用到。