欧拉函数

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


本文章由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)!=1p<=i,而p又是质数,所以i\ mod\ p==0,则可知\phi(i)中已经有(1-\frac{1}{p})这一项了,所以可以不用再乘了。同时,执行完这一句后就break了,这是因为为了保证每一个数i*p只能由它的最小的质因子p筛到,这时线性筛的复杂度保证。

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:欧拉函数


HNCJ OIer 一枚