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

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

欧拉函数的值

一般方法

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

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

需要注意：$\varphi(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{align}\\ \varphi(n)=n&-\frac{n}{p_1}-\frac{n}{p_2}-\cdots-\frac{n}{p_r}\\ &+\frac{n}{p_1p_2}+\frac{n}{p_1p_3}+\cdots+\frac{n}{p_{r-1}p_r}\\ &-\frac{n}{p_1p_2p_3}-\frac{n}{p_1p_2p_4}-\cdots-\frac{n}{p_{r-2}p_{r-1}p_r}\\ &\cdots\cdots \end{align} $$

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

程序实现

该方法仅求得 $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$ 外互素，因此 $\varphi(i)=i-1$

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

$$ \begin{align}\\ \varphi(i)&=(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_r})\cdot i\\ \varphi(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\varphi(i\cdot prime[j])&=\varphi(i)\cdot prime[j]\\ \end{align} $$

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

$$ \begin{align}\\ \varphi(i)&=(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_r})\cdot i\\ \varphi(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\varphi(i\cdot prime[j])&=\varphi(i)\cdot prime[j]\cdot (1-\frac{1}{prime[j]})=\varphi(i)(prime[j]-1)\\ \end{align} $$

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

程序实现

该方法求得 $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);
        }
    }
}