学习笔记--数论--欧拉函数φ( )

Rye_Catcher · 2018-02-15 23:01:29 · 个人记录

• 什么是欧拉函数

在数论，对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。欧拉函数用希腊字母φ()或phi() （念fai去声）表示，phi（n）表示正整数n的欧拉函数。

      举个栗子：[1,12]中与12互质的有1,5,7,11。
      (别忘了，a与b互质表示gcd(a,b)=1，故1也算)
      所以φ(12)=4。

• 怎么算？

首先用暴力的方法不用多讲，时间复杂度为O（N），实在是不尽人意，那有没有更好的方法呢？？？ 这有个式子： 对于一个正整数n，若n=p1^q1×p2^q2×...×pn^qn.

嗯，是不是看不懂？ 首先我们需要这个

     这个公式的证明不难得出：

     p^k可整除p,2p,3p(雾)...p*p...p^(k-1)*p，故它的质因子个数为p^k-p^(k-1)。

     这只是第一步，我们还需要知道欧拉函数是个不完全积性函数，仅对于两个互质的数p,q，存在：

     φ(p*q)=φ(p)*φ(q)

     emmmmm然而这个证明本蒟蒻并不会，只能麻烦各位自己动手了

     但是有了这个前提，我们就知道：

     φ(p1^q1*p2^q2*...*pn^qn)
     =φ(p1^q1)*φ(p2^q2)*...*φ(pn^qn)
     =(p1^q1-p1^(q1-1))*(p2^q2-p2^(q2-1))*...(pn^qn-pn^(qn-1))
     =p1^q1*p2^q2*...*pn^qn*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
     =n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)

• 实现

  给出任意正整数n，求φ(n).

  见《算法竞赛入门经典（第二版）》

  int euler_phi(int n)
  {
    int m=(int)sqrt(n+0.5);
    int ans=n;
    for(register int i=2;i<=m;i++)
        if(n%i==0)
        {//最好要先除后乘，防止结果溢出 
          ans=ans/i*(i-1);   //上文推导得 
          while(n%i==0)n=n/i;//将n中所有因子i筛去 
                           //确保下一个i是n的质因子 
        }
    if(n>1)ans=ans/n*(n-1);//防止n为最后一个质因子 
    return ans;
  }

  例题： hdu 1787裸欧拉函数简单变式

  参考博客：orz orz orz