欧拉函数,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。
这是我在ACM队内训练赛的时候遇到的一个函数,其实最初是在离散数学课本上了解到了这个函数,但是当时并没有留下太深的印象,现在总结一下。首先要知道欧拉函数的公式:euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn)其中p1,p2,p3是x的所有质因子。1.第一种算法:直接求法:暴力遍历x的所有质因子直接求解:int euler(int n){ //返回euler(n) int res=n,a=n; for(int i=2;i*i<=a;i++){ if(a%i==0){ res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; }
其中while(a%i==0) a/=i;
是在进行保证可以整除的是素数的过程。
for(int i=2;i*i<=a;i++)
也利用了素数筛选法的思想。 2.第二种算法:
筛选法打表求欧拉函数#define Max 1000001 int euler[Max]; void Init(){ euler[1]=1; for(int i=2;i
打表求值,不断求得。
2017-06-26 17:43:32 星期一 更新
今天在《算法竞赛入门(第二版)》(紫书)上看到了一种利用类似与素数筛选法的方法直接求由1~n的所有欧拉函数值的办法。给出代码:int pi[50001+10];const int maxn=50001;int euler(int n){ memset(pi,0,sizeof(pi)); pi[1]=1; for(int i=2;i<=n;i++) if(!pi[i]) { for(int j=i;j<=n;j+=i) { if(!pi[j]) pi[j]=j; pi[j]=pi[j]/i*(i-1); } }}
利用这个办法可以在nloglogn的复杂度内求得由1到n的所有欧拉函数值。
2017-08-09 12:48:12
新增一些欧拉函数的性质:
1.如果一个数x是素数,则该数的欧拉函数值为x-1。
2.若m,n互质,
3.当n为奇数时,