欧拉函数

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


本文章由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$$的因子,累计到答案里即可

ll Phi(ll x)//求φ
{
    ll ret=x;
    for (ll i=2;i*i<=x;i++)
        if (x%i==0)//找到一个质因子
        {
            ret=ret/i*(i-1);
            while (x%i==0) x=x/i;//把x除干净
        }
    if (x>1) ret=ret/x*(x-1);
    return ret;
}

线性筛求法

当我们要求$$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]$$
这里首先给出线性求欧拉函数的算法

//notprime[i]为0表示是质数,为1表示不是质数
//Prime[]存放已经筛出来的质数
//maxNum值域
void GetPhi()
{
    notprime[1]=1;phi[1]=1;//设置初始值
    for (int i=2;i<maxNum;i++)
    {
        if (notprime[i]==0) phi[i]=i-1,Prime[++pricnt]=i;
        for (int j=1;(j<=pricnt)&&((ll)Prime[j]*i<maxNum);j++)
        {
            notprime[i*Prime[j]]=1;
            if (i%Prime[j]==0)
            {
                phi[i*Prime[j]]=phi[i]*Prime[j];
                break;
            }
            phi[i*Prime[j]]=phi[i]*phi[Prime[j]];
        }
    }
    return;
}

然后我们现在给出欧拉函数的递推公式(下文中的$$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 一枚