欧拉函数

发布于 2018-01-11  459 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:欧拉函数

欧拉函数

定义

定义\(\phi(i)\)为不大于\(i\)的与\(i\)互质的数的个数,公式表达为
\[\sum_{i=1}^{n-1}[gcd(i,n)==1]\]
规定:\(\phi(1)=1\)

基本计算公式

\[\phi(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})\]其中\(p_1,p_2....p_n\)为\(x\)的质因子
这个公式比较直观,即对于数\(x\)来说,有\(x-1\)个比它小的数,枚举\(x\)的因子在这些数中删去它们,最后剩下的就是与\(x\)互质且小于x的数了

基本性质

性质1

对于任意质数\(p\),\(\phi(p)=p-1\)

证明:这个比较好想,对于任意一个质数,小于它的数都与它互质

性质2

对于任意质数$$p$$,$$\phi(p^k)=(p-1)*p^{k-1}$$

证明:根据基本公式$$\phi(p^k)=p^k*(1-\frac{1}{p})=p^k*\frac{p-1}{p}=p^{k-1}$$

性质3

$$\phi(xy)=\phi(x)*\phi(y)$$其中$$gcd(x,y)==1$$

这个可以由欧拉函数是积性函数推出来

#欧拉函数的求法
知道了上面的若干性质,有什么用呢?它们可以用来求解欧拉函数

单个欧拉函数的求法

直接运用基本公式求解。对于数$$x$$分解出它的每一个质因子$$p$$,依次计算即可
由于考虑到一个数$$x$$最多只会有一个大于$$\sqrt{x}$$的因子,所以可以只枚举到$$\sqrt{x}$$,那么如果最后还剩下一个非$$1$$的因子,累计到答案里即可

线性筛求法

当我们要求$$1...n$$每一个数的欧拉函数时,上面的复杂度就过高了。而我们知道在筛素数的时候有线性素数筛的方法,那么欧拉函数时候有线性筛的算法呢?
有,不过在此之前我们先说一说能线性筛的原理
基本条件:
$$\phi(p)=p-1$$其中$$p$$是质数
$$\phi(p^k)=(p-1)*p^{k-1}$$
欧拉函数是积性函数,即$$\phi(pq)=\phi(p)*\phi(q) [gcd(p,q)==1]$$
这里首先给出线性求欧拉函数的算法

然后我们现在给出欧拉函数的递推公式(下文中的$$p$$均为质数且保证$$p<=i$$(这个是$$for$$循环从小到大能够保证的))
$$ \phi(i*p)= \begin{cases}p-1 \quad i==1 \\ \phi(i)*\phi(p) \quad gcd(i,p)==1 \\ \phi(i)*p \quad gcd(i,p)!=1 \end{cases} $$

第一条不需要多解释,根据性质一可以直接得到
第二条同样,由性质三积性函数可以得到
第三条作如下说明
因为$$gcd(i,p)!=1$$且$$p<=i$$,而$$p$$又是质数,所以$$i\ mod\ p==0$$,则可知$$\phi(i)$$中已经有$$(1-\frac{1}{p})$$这一项了,所以可以不用再乘了。同时,执行完这一句后就$$break$$了,这是因为为了保证每一个数$$i*p$$只能由它的最小的质因子$$p$$筛到,这时线性筛的复杂度保证。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:欧拉函数


HNCJ OIer