欧拉函数：对正整数 $n$，欧拉函数是小于 $n$ 的正整数中与 $n$ 互质的数的数目，记作 $\phi (n)$。

例如，$\phi (8)=4$，因为 $1,3,5,7$ 均与 $8$ 互质。注意：$\phi (1)=1$

欧拉函数的值

一般方法

若 $n$ 有标准分解 $p_1^{k_1}{p}_2^{k_2}\cdots p_r^{k_r}$，其中 $p_i$ 为互异的质因子，$k_i\ge 1$ 为质因子的次数。则欧拉函数的值为：

$$\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})$$

需要注意：$\phi (1)=1$

简单证明

若要获得 $1\sim n$ 中的质因子个数，可以将 $n$ 减去 $p_1$ 和它的倍数的数量，减去 $p_2$ 和它的倍数的数量 $\cdots \cdots$

写成表达式即为：

$$n-\frac{n}{p_1}-\frac{n}{p_2}-\cdots -\frac{n}{p_r}$$

但是可以发现，$p_1,p_2$ 的公倍数、$p_1,p_3$ 的公倍数 $\cdots \cdots$ 被减去了两次，因此需再加上一次。但又发现 $p_1,p_2,p_3$ 的公倍数、$p_1,p_2,p_4$ 的公倍数 $\cdots \cdots$ 多加了一次，得再减去一次，这便是容斥原理的思维。

最终表达式为：

$$\begin{array}{r}\\ \phi (n)=n& -\frac{n}{p_1}-\frac{n}{p_2}-\cdots -\frac{n}{p_r}\\ & +\frac{n}{p_1{p}_2}+\frac{n}{p_1{p}_3}+\cdots +\frac{n}{p_{r-1}{p}_r}\\ & -\frac{n}{p_1{p}_2{p}_3}-\frac{n}{p_1{p}_2{p}_4}-\cdots -\frac{n}{p_{r-2}{p}_{r-1}{p}_r}\\ & \cdots \cdots \end{array}$$

通过化简即可得到结果式子的形式。

程序实现

该方法仅求得 $n$ 的欧拉函数值

• 时间复杂度：$O(\sqrt{n})$
• 空间复杂度：$O(1)$

编程时需要注意的是，$\frac{1}{p_i}$ 会被整除得到 $0$，因此需将 $1-\frac{1}{p_i}$ 变形为 $\frac{p_i-1}{p_i}$。同时，对 $n$ 先除再乘，防止溢出。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a;
    cin >> a;
    int ans = a;
    for (int i = 2; i <= a / i; i++)
    {
        if (!(a % i))
        {
            ans = ans / i * (i - 1);
            while (!(a % i))
                a /= i;
        }
    }
    if (a > 1)
        ans = ans / a * (a - 1);
    cout << ans << endl;
    return 0;
}

线性筛法

简单证明

通过简单改造线性筛，再筛得质数的同时计算出欧拉函数值。线性筛中有三种情况：

1. $i$ 为质数
2. $i$ 能被 $prime[j]$ 整除
3. $i$ 不能被 $prime[j]$ 整除

我们分类讨论：

当 $i$ 为质数时，$i$ 与除 $1$ 外互素，因此 $\phi (i)=i-1$

当 $i$ 能被 $prime[j]$ 整除时，$prime[j]$ 即为 $i$ 的一个质因子，那么 $i\cdot prime[j]$ 的标准分解的质因子和 $i$ 完全一样，那么：

$$\begin{array}{r}\\ \phi (i)& =(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})\cdot i\\ \phi (i\cdot prime[j])& =(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})\cdot i\cdot prime[j]\\ \Rightarrow \phi (i\cdot prime[j])& =\phi (i)\cdot prime[j]\end{array}$$

当 $i$ 不能被 $prime[j]$ 整除时，$prime[j]$ 不时 $i$ 的质因子，但是 $i\cdot prime[j]$ 的一个质因子，那么：

$$\begin{array}{r}\\ \phi (i)& =(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})\cdot i\\ \phi (i\cdot prime[j])& =(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})(1-\frac{1}{prime[j]})\cdot i\cdot prime[j]\\ \Rightarrow \phi (i\cdot prime[j])& =\phi (i)\cdot prime[j]\cdot (1-\frac{1}{prime[j]})=\phi (i)(prime[j]-1)\end{array}$$

按照上面的转换方式修改线性筛的代码即可。

程序实现

该方法求得 $1\sim n$ 的所有欧拉函数值

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

const int MAXN = 1e6 + 10;
int prime[MAXN], phi[MAXN], idx;
bool is_prime[MAXN];

void init(int n)
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            prime[idx++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < idx && i * prime[j] <= n; j++)
        {
            is_prime[i * prime[j]] = false;
            if (!(i % prime[j]))
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}