快速幂

顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

原理

以下以求a的b次方来介绍，把幂指数b转换成二进制数。该二进制数第i位的权为2^(i-1)， 例如11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1。因此，我们将a¹¹转化为算


代码比较

1
2
3
4
5
6
//常规求幂，STL里面有pow函数求幂，如3^6为pow(3, 6)。
int pow1(int a,int b){
   int r=1;
   while(b--) r*=a;
   return r;
}
1
2
3
4
5
6
7
8
9
10
//快速求幂（一般）
int pow2(int a,int b){
    int r=1,base=a;
    while(b!=0){
    if(b%2) r*=base;
    base*=base;
    b/=2;
    }
    return r;
}
1
2
3
4
5
6
//快速求幂 （递归）
int f(int m,int n){   //m^n
    if(n==1) return m;
    int temp=f(m,n/2);
    return (n%2==0 ? 1 : m)*temp*temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//快速求幂（位运算）
int pow3(int x,int n){
  if(n==0) return 1;
  else {
    while((n&1)==0){
      n>>=1;
      x*=x;
    }
  }
  int result=x;
  n>>=1;
  while(n!=0){
    x*=x;
    if(n&1) result*=x;
    n>>=1;
  }
  return result;
}
1
2
3
4
5
6
7
8
9
10
快速求幂（位运算，更简洁，跟一般快速幂是一样的，即pow2 ）
int pow4(int a,int b){
  int r=1,base=a;
  while(b){
    if(b&1) r*=base;
    base*=base;
    b>>=1;
  }
  return r;
}

快速幂取模

(ab)%c=(a%c)(b%c)%c 

1
2
3
4
5
6
7
8
9
10
11
12
int quick(int a,int b,int c)  
{  
    int ans=1;   //记录结果  
    a=a%c;   //预处理，使得a处于c的数据范围之下  
    while(b!=0)  
    {  
        if(b&1) ans=(ans*a)%c;   //如果b的二进制位不是0，那么我们的结果是要参与运算的  
        b>>=1;    //二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位  
        a=(a*a)%c;   //不断的加倍  
    }  
    return ans;  
}