数据结构与算法分析 - 快速幂简介

（1）.秦九韶算法：

把一个N次的多项式，改写成如下形式：

（2）.快速幂算法

（3）.代码模板：

   1:  //整数的快速幂 m^n  % k 的快速幂： 

   2:  long long  quickpow(long long   m , long long   n , long long   k){ 

   3:      long long   ans = 1; 

   4:      while(n){ 

   5:          if(n&1)//如果n是奇数 

   6:              ans = (ans * m) % k; 

   7:          n = n >> 1;//位运算“右移1类似除1” 

   8:          m = (m * m) % k; 

   9:      } 

  10:      return ans; 

  11:  } 

 

（4）.代码解释：

（5）.样例实验

hdu 2035 - 人见人爱A^B

题意：求解(A^B）%1000

解法：自然是快速幂。

附上我的代码：

   1:  #include<cstdio>

   2:  #include<cstdlib>

   3:  using namespace std;

   4:  //计算（a^p）%m

   5:  long long int fast_pow(long long a,long long p,long long m){

   6:      long long ans=1;

   7:      while(p){

   8:          if(p&1) ans=(ans*a)%m;

   9:          p=p>>1;

  10:          a=(a*a)%m;

  11:      }

  12:      return ans;

  13:  }

  14:  int main(){

  15:      int n,m;

  16:      while(scanf("%d %d",&n,&m)!=EOF && (n||m)){

  17:          printf("%d\n",fast_pow(n,m,1000));

  18:      }

  19:  }

数据结构与算法分析 - 快速幂简介,布布扣,bubuko.com

数据结构与算法分析 - 快速幂简介

原文：http://www.cnblogs.com/ZJUT-jiangnan/p/3656279.html