模幂运算

概念：
　　模运算即求余运算。“模”是“Mod”的音译，模运算多应用于程序编写中。 Mod的含义为求余。模运算在数论和程序设计中都有着广泛的应用，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒密码问题，无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍，但多数都是以纯理论为主，对于模运算在程序设计中的应用涉及不多。
　　模幂运算则是指先进行幂运算，在进行模运算。

算法：
1)描述:
　　根据运算规则ab % p = ((a % p)b) % p ，我们知道3333^5555（%10）= 3^5555（%10）。由于3^4 = 81，所以3^4（%10）= 1。
　　根据运算规则（3） (a * b) % p = (a % p * b % p) % p ，由于5555 = 4 * 1388 + 3，我们得到3^5555（%10）=（3^(4*1388) * 3^3）（%10）=（（3^(4*1388)（%10）* 3^3（%10））（%10）=（1 * 7）（%10）= 7。
　　计算完毕。
　　利用这些规则我们可以有效地计算X^N(% P)。简单的算法是将result初始化为1，然后重复将result乘以X，每次乘法之后应用%运算符（这样使得result的值变小，以免溢出），执行N次相乘后，result就是我们要找的答案。
　　这样对于较小的N值来说，实现是合理的，但是当N的值很大时，需要计算很长时间，是不切实际的。下面的结论可以得到一种更好的算法。
　　如果N是偶数，那么X^N =（X*X）^[N/2]；
　　如果N是奇数，那么X^N = X*X^(N-1) = X *（X*X）^[N/2]；
　　其中[N]是指小于或等于N的最大整数。 
2)源码:

View Code

 1 // 函数功能：利用模运算规则，采用递归方式，计算X^N(% P)
 2 // 函数名：PowerMod
 3 // 输入值：unsigned int x，底数x
 4 // unsigned int n，指数n
 5 // unsigned int p，模p
 6 // 返回值：unsigned int，X^N(% P)的结果
 7 unsigned int PowerMod(unsigned int x, unsigned int n, unsigned int p)
 8 {
 9 if (n ==0)
10     {
11 return1;
12     }
13     unsigned int temp = PowerMod((x * x)%p, n/2, p); //递归计算（X*X）^[N/2]
14 if ((n &1) !=0) //判断n的奇偶性
15     {
16         temp = (temp * x) % p;
17     }
18 return temp;
19 }  

【参考资料 感谢作者】
模运算_百度百科:http://baike.baidu.com/view/2385246.htm#2