【算法】求欧拉函数（包括完整的证明以及代码模板，建议收藏）

求欧拉函数

前置知识

互质：互质是公约数只有1的两个整数，叫做互质整数。

欧拉函数定义

$1\sim N-1$中与N互质的数的个数被称为欧拉函数，记为$\varphi (N)$。

若在算数基本定理中，$N=p_1^{a_1}{p}_2^{a_2}...p_m^{a_m}$，则：

$\varphi (N)=N\cdot \frac{p_1-1}{p_1}\cdot \frac{p_2-1}{p_2}\cdot ...\cdot \frac{p_m-1}{p_m}$

欧拉函数推导

首先我们要知道$1,2,\mathrm{3...}N-1,N$与$N$互质的个数是$1\sim N$数列去除N的质因子的倍数。

例如$N=10,即1,2,3,4,5,6,7,8,9,10$去除$N$的质因子的倍数$,则1,\bcancel{2},3,\bcancel{4},\bcancel{5},\bcancel{6},7,\bcancel{8},9,\bcancel{10}.$

显然，$1,3,7,9$与$10$互质。

由上方结论使用容斥原理进行数学推导如下：

$\because N=p_1^{a_1}{p}_2^{a_2}...p_m^{a_m}$

①.从1~n中去掉$p_1,p_2,...,p_k$的所有倍数的个数，即

$n\leftarrow n-\frac{n}{p_1}-\frac{n}{p_2}-...-\frac{n}{p_k}$

②.由容斥原理，$p_i\cdot p_j$的倍数个数被①减了两次，所以加上所有$p_i\cdot p_j$的倍数的个数（其中$p_i,p_j$是$p_1\sim p_k$的排列），即

$n\leftarrow n+\frac{n}{p_1\cdot p_2}+\frac{n}{p_1\cdot p_3}+...+\frac{n}{p_{k-1}\cdot p_k}$

③.减去所有$p_i\cdot p_j\cdot p_k$的倍数个数，即

$n\leftarrow n-\frac{n}{p_1\cdot p_2\cdot p_3}-\frac{n}{p_1\cdot p_2\cdot p_4}-...-\frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k}$

④.同理，加上所有$p_i\cdot p_j\cdot p_k\cdot p_l$的倍数个数，即

$n\leftarrow n+\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_4}+\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_5}+...+\frac{n}{p_{k-3}\cdot p_{k-2}\cdot p_{k-1}\cdot p_k}$
KaTeX parse error: Can't use function '\mathord' in text mode at position 1: \̲m̲a̲t̲h̲o̲r̲d̲{\varvdots\rule…
因此，
$$\begin{gathered} \varphi (n)=n-\frac{n}{p_1}-\frac{n}{p_2}-...-\frac{n}{p_k} \\ +\frac{n}{p_1\cdot p_2}+\frac{n}{p_1\cdot p_3}+...+\frac{n}{p_{k-1}\cdot p_k} \\ -\frac{n}{p_1\cdot p_2\cdot p_3}-\frac{n}{p_1\cdot p_2\cdot p_4}-...-\frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k} \\ +\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_4}+\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_5}+...+\frac{n}{p_{k-3}\cdot p_{k-2}\cdot p_{k-1}\cdot p_k} \\ -... \end{gathered}$$
也就是n减去奇数个质因子的倍数个数，加上偶数个质因子的倍数个数，循环往复。

将上式等价变形，得到

$\varphi (n)=n\cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2})...\cdot (1-\frac{1}{p_k})$

证必。

代码模板

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