欧拉函数相关

说是数论只会gcd的我其实真的遇到，连gcd都不会，怎么办呢！那就看欧拉函数压压惊吧。

一、定义：

一个正整数的欧拉函数定义为小于它且与它互质的正整数的个数。(φ(1)=1)

二、性质：

1、对于质数p，φ(p)=p-1

2、\(\varphi (x)=x(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})(1-\frac{1}{p_{3}})……(1-\frac{1}{p_{n}})\)，其中p1,p2,p3,…,pn为x的质因子

3、若\(n=p^{k}\)，则\(\varphi (n)=p^{k}-p^{k-1}=(p-1)p^{k-1}\)

4、当n为奇数时，φ(2n)=φ(n)

5、欧拉函数是积性函数，若p,q互质，则φ(pq)=φ(p)φ(q)

6、推广：设p为素数且p|n，若p^2|n，则\(\varphi (n)=\varphi (\frac{n}{p})*p\)，否则\(\varphi (n)=\varphi (\frac{n}{p})*(p-1)\)

三、应用

1、求单个数的欧拉函数值

求单个数n的欧拉函数值思路就是先将n分解质因数然后利用性质3和5相乘计算

复杂度\(O(\log{N})\)

2、求1-n的欧拉函数表

与素数筛类似，一边筛素数一边计算欧拉函数值，具体的实现利用了上述性质6

复杂度\(O(N)\)

3、指数降幂公式

\(A^{n}\mod{p}=A^{n\mod{\varphi (p)+\varphi (p)}}\mod{p}\)

丢个公式就跑，真tm刺激