高次方求模

2019-04-13 16:32发布

有了这个公式,求解问题就简单了,np次方很容易拆分为几个数相乘的形式。其中采用二分法拆分较为简单高效。
递归: [cpp] view plaincopyprint?
  1. #define M 10003  
  2.   
  3. int PowMod(int n, int p)  
  4. {  
  5.     if (p == 1)  
  6.     {  
  7.         return n % M;  
  8.     }  
  9.     int temp = Pow(n, p/2);  
  10.     int result = (temp*temp) % M;  
  11.     if (p % 2 == 1)  
  12.     {  
  13.         result = (result*n) % M;  
  14.     }  
  15.     return result;  
  16. }  
非递归: [cpp] view plaincopyprint?
  1. #define M 10003  
  2.   
  3. int PowMod(int n, int p)  
  4. {  
  5.     int result = 1;  
  6.     while (p > 0)  
  7.     {  
  8.         if (p % 2 == 1)  
  9.         {  
  10.             result = (result*n) % M;  
  11.         }  
  12.         p /= 2;  
  13.         n = (n*n) % M;  
  14.     }  
  15.     return result;  


From: http://blog.csdn.net/code_pang/article/details/7989356