欧拉定理及其应用(注解版)~~yt

《欧拉定理及其应用(注解版)~~yt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、欧拉定理及其应用                                      欧拉函数phi(m)表示小于等于

2、m

3、的自然数中，和m互质的数的个数。phi(m)=mΠ(1-1/p)//《算法导论》第531页      p

4、m证明：若m为一素数p，则phi(m)=p-1。若m为合数，存在p，使m=pd。1、若p整除d，对任意a，(a,d)=1，//注意a属于[1,d)那么(a+d,d)=1，(a+d,p)=1，所以(a+d,m)=1，所以(a+kd,m)=1，k=0,1,2,...,p-1，所以

5、phi(m)=pphi(d)。//则有任意和d互质的数加上kd继续互质，所以共有p*phi(d)个2、若p不能整除d，那么(p,d)=1，在小于

6、m

7、的自然数里，和d互质的有pphi(d)个，其中phi(d)个是p的倍数，所以phi(m)=(p-1)phi(d)。//显然，除d、2d、3d……pd能整除外，其余都不能整除由数学归纳法得到结论。欧拉定理：如果(a,m)=1，那么a^phi(m)=1(modm)。//可以参考《算法导论》证明：设R(m)={r[1],r[2],...,r[phi(m)]}为和m互

8、质的数的等价类的集合。那么有(ar[i],m)=1，ar[i]=ar[j]当且仅当i=j。所以aR(m)={ar[i]}=R(m)，a^phi(m)Πr[i]=Πar[i]=Πr[i](modm)，a^phi(m)=1(modm)。欧拉定理的一个重要意义就是计算a^bmodm的时候，若b是一个很大的数时，可以化成a^(bmodphi(m))modm来计算，明显地，bmodphi(m)是一个比较小的数。当(a,m)≠1时，设对m分解质因数得到m=Πpi^ri，d=(a,m)，m=m1*m2，其中m1=Πpi^

9、ri，那么(m1,m2)=1，(a,m2)=1，       pi

10、d所以a^phi(m2)=1(modm2)。由欧拉函数的计算公式可以得知phi(m2)

11、phi(m)，所以a^phi(m)=1(modm2)。对任意i，pi

12、d，都有phi(m)>=logm>=ri，所以m1

13、d^phi(m)，m1

14、a^phi(m)。由于(m1,m2)=1，所以存在整数r，0

15、)=0(modm1)，所以a^2phi(m)=a^phi(m)(modm)。因此，即使(a,m)≠1，也能很快地得到a^bmodm的结果。例题1：TCSRM273FactorialTower计算a[0]!^a[1]^a[2]!^...^a[n-1]!modm//递归得到，/*a[0]^a[1]^a[2]^…^a[n-1]modm等价于先求出phi（m）令m1=phi(m),再用a[1]^a[2]^…^a[n-1]mod(m1)，等价于先求出phi(m1),令m2=phi(m1)，再用a[2]^a[3]^…^

16、a[n-1]mod(m2)，等价于先求出phi(m2),令m3=phi(m2),……最后就有a[n-1]mod(m[n-1])。。。逆向返回*//*注意，上面我们只是单方面用了递归思想，还要考虑下m1>m2>m3……所以至多在m-1步之后，m[m-1]=1（至于为什么为1，而不是0，显然哈~~这儿不做详细解释了），所以更高阶的将不需要计算,我只是给出了上界，下面我将修正它**********/根据前面的结论，可以通过递归计算得到结果。每一步里面，计算phi(m)的复杂度为O(sqrt(m))，计算a[i]^

17、bmodm复杂度为O(a[i]+logm)//a^bmodm==a^(bmodphi(m))modm由于a[i]

18、**的上界就可以修正为logm了。。所以只要min{O(logm),n}步就能完成整个过程。因此，整体复杂度为O(mlogm)。//显然啦~~~例题2：StrangeLimit设a1=p，p为一质数，an+1=p^an，bn=anmodm!，给出p,m，2<=p,m<=12，求limbn，1<=n,m,t<=100