欧拉函数φ(n)是1~n-1的与n互质的数的个数 欧拉函数公式:φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*...*(1-1/pn);这里的pi是n的所有质因数,n>0。 欧拉定理:若n为素数,φ(n)=n-1。 若n的另一个素数p的a次幂,φ(p^a)=(p-1)*p^(a-1),比p^a小的数有p^a-1个,那么有p^(a-1)-1个数能被p所整除(1~p^a-1中p的倍数一共p^(a-1)-1个)。φ(p)=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)。 如果n为任意两个数a和b的积,那么φ(a*b)=φ(a)*φ(b) 若n为奇数,则φ(2n)=φ(n); 我们可以把欧拉函数的通式改写为:φ(n)=(n-n*p1)...(1-1/pn),然后下面的欧拉函数的程序应该就好理解了。
第一个找到的i一定是质因数,while(n%i==0)n/=i;是完全消除i这个质因子(参考n=(p1^a1)*(p2^a2)*……*(pk^ak) (为N的分解式),pi是质因子)。 还有素数表实现的代码: 先把50 000以内的素数用筛选法选出来并保存,以方便欧拉函数使用,这样,在不考虑筛选法的时间复杂度,而单纯看欧拉函数,其复杂度为O(x),x为O(√¯n)以内素数的个数。
有时候我们遇见频繁调用欧拉函数的题时,我们通常回预处理所有欧拉函数出来,用下面的递推式。
另有一些题目中可能用的性质 转自劢臻佳境 N>1,不大于N且和N互素的所有正整数的和是 1/2*M*eular(N)。 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a; 若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1); 来源:http://www./content-4-156801.html |
|