高次方求模

2019-04-13 16:32发布

站内文章 / 模拟电子
10772 0 1422
有了这个公式，求解问题就简单了，n的p次方很容易拆分为几个数相乘的形式。其中采用二分法拆分较为简单高效。
递归： [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;  
  16. } 

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

热门文章