前置知识

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

欧拉函数定义

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

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

$\phi(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,3…N-1,N$与$N$互质的个数是$1∼N$数列去除N的质因子的倍数。

例如$N=10,即1,2,3,4,5,6,7,8,9,10$去除$N$的质因子的倍数,则1,2,3,4,5,6,7,8,9,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←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∼p_k$的组合），即

$n←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←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←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}}$
$$\textbf{⋮}$$
因此，
$$\phi(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}}\\ -…$$
也就是n减去奇数个质因子的倍数个数，加上偶数个质因子的倍数个数，循环往复。

将上式等价变形，得到

$\phi(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;
}