繁荣空间里.doc

欧拉函数phi(m)表示小于等于|m|的自然数中,和m互质的数的个数。
phi(m)=mΠ(1-1/p)
       p|m
证明:若m为一素数p,则phi(m)=p-1。
若m为合数,存在p,使m=pd。
若p整除d,对任意a,(a, d) = 1,那么(a + d, d) = 1,(a + d, p) = 1,
所以(a + d, m) = 1,所以(a + kd, m) = 1,k = 0, 1, 2, ... , p - 1,
所以phi(m) = p phi(d)。
若p不能整除d,那么(p, d) = 1,在小于|m|的自然数里,和d互质的有p phi(d)个,
其中phi(d)个是p的倍数,所以phi(m) = (p - 1) phi(d)。
由数学归纳法得到结论。
欧拉定理:如果(a, m) = 1,那么a ^ phi(m) = 1 (mod m)。
证明:设R(m) = {r[1], r[2], ... , r[phi(m)]}为和m互质的数的等价类的集合。
那么有(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] (mod m),a ^ phi(m) = 1 (mod m)。
欧拉定理的一个重要意义就是计算a ^ b mod m的时候,若b是一个很大的数时,
可以化成a ^ (b mod phi(m)) mod m来计算,明显地,b mod phi(m)是一个比较小的数。
当(a, m)≠1时,设对m分解质因数得到m = Πpi ^ ri,d = (a, m),m = m1 * m2,
其中m1 = Πpi ^ri,那么(m1, m2) = 1,(a, m2) = 1,
        pi|d
所以a ^ phi(m2) = 1 (mod m2)。
由欧拉函数的计算公式可以得知phi(m2)|phi(m),所以a ^ phi(m) = 1 (mod m2)。
对任意i,pi|d,都有phi(m) >= log m >= ri,所以m1|d ^ phi(m),m1|a ^ phi(m)。
由于(m1, m2) = 1,所以存在整数r,0 < r < m,r = 1 (mod m2),r = 0 (mod m1),
有a ^ phi(m) = r (mod m)。
显然,a ^ 2phi(m) = 1 (mod m2),a ^ 2phi(m) = 0 (mod m1),
所以a ^ 2phi(m) = a ^ phi(m) (mod m)。
因此,即使(a, m)≠1,也能很快地得到a ^ b mod m的结果。
例题1:TC SRM273 FactorialTower
计算a[0]! ^ a[1] ^ a[2]! ^ ... ^ a[n - 1]! mod m
根据前面的结论,可以通过递归计算得到结果。
每一步里面,计算phi(m)的复杂度为O(sqrt(m)),计算a[i] ^ b mod m复杂度为O(a[i] + log m)
由于a[i] < m,所以一步的复杂度为O(m)。
若m为偶数,则phi(m) <= m