2016-12-7 关于欧拉函数

关于什么是欧拉函数，以及一些非常简单的欧拉函数，在此就不多加赘述。

欧拉函数的基本性质：

1.欧拉函数是积性函数,但不是完全积性函数,即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立.

2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.

  则： φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

3.除了N=2,φ(N)都是偶数.

4.设N为正整数,∑φ(d)=N (d|N).

另外：欧拉函数的编程应用公式：

1.P为素数,φ(P)=P-1.

2.若i mod prime[j]=0,那么φ(i*prime[j])=φ(i)*prime[j]

3.若i mod prime[j]≠0,那么φ(i*prime[j])=φ(i)*(prime[j]-1)

在打欧拉函数表的时候，可以用到新学的筛选法求素数的附加条件：

#include

using namespace std;

bool a[100000];

int phi[100000];

int prime[100000];

int n;

void phi1(){

 int size=0;

 for(int i=2;i

  if(a[i]){

   phi[i]=i-1;

   prime[size++]=i;

  } 

  int j=0;

  while(j<=size&&j*i

   a[i*prime[j]]=0;

   if(i%prime[j]==0) {

    phi[i*prime[j]]=phi[i]*prime[j];

    break;

   }

   else phi[i*prime[j]]=phi[i]*(prime[j]-1);

   j++;

  }

 }

 for(int i=0;i

 cout<

}

int main()

{

    memset(a,1,sizeof(a));

    cin>>n;

    phi1();

    return 0;

}

这样，线性筛欧拉函数的时间复杂度就会仅仅为O（n），并且没有重复筛选的phi。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！