欧拉函数
定义
\(\phi(n)\)表示不大于n的正整数的数的个数中与n互素的数的个数，即n的完全剩余系的大小
性质
1.若n为质数，则\(\phi(p)=p-1\)
2.若n为质数，则\(\phi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\)
3.积性:若\((n,m)=1\)，则\(\phi(mn)=\phi(n)\phi(m)\)
性质1:显然。
性质2: \([1,p^k]\) 中与 \(p^k\) 不互质的数有 \(p,2p,3p...p^2...p^k\) 共 \(p^{k-1}\) 个数，则 \(\phi(p^k)=p^k-p^{k-1}\)
性质3:......
计算公式
由唯一分解定理\(n=\prod_{i=1}^sp_i^{a_i}=p_1^{a_1}p_2^{a_2}...p_s^{a_s}\)
\(\begin{align}
\phi(n)
&=p_1^{a_1}p_2^{a_2}...p_s^{a_s}\notag\\
&=\phi(p_1^{a_1})\phi(p_2^{a_2})...\phi(p_s^{a_s})\notag\\
&=p_1^{a_1-1}(p_1-1)p_1^{a_2-1}(p_2-1)...p_1^{a_s-1}(p_s-1)\notag\\
&=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_s})\notag
\end{align}\)
例题
P2158 [SDOI2008] 仪仗队
模板题