前置知识
互质:互质是公约数只有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;
}