快速冪，快速冪取模
快速冪顧名思義，就是快速算某個數的多少次冪。其時間復雜度為 O(log₂N)， 與樸素的O(N)相比效率有了極大的提高。
原理：
以下以求a的b次方來介紹
把b轉換成二進制數。
如：
=
11的二進制是1011
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1
因此，我們將a¹¹轉化為算
![]()
代碼比較：
常規求冪
![]()
1 int pow1(inta,intb){
2 int ans=1;
3 while(b--)
4 ans*=a;
5 return ans;
6 }
View Code
二分求冪（一般）
![]()
1 int pow2(inta,intb){
2 int ans=1 , temp=a;
3 while(b){
4 if(b%2)
5 ans*=temp;
6 temp*=temp;
7 b/=2;
8 }
9 return ans;
10 }
View Code
快速求冪（位操作）
![]()
1 int pow3(inta,intb){
2 int ans = 1 , temp = a ;
3 while(b){
4 if(b&1) //b%2 = b&1
5 ans*=temp;
6 temp*=temp;
7 b>>=1; //b/2 = b>>1
8 }
9 return ans;
10 }
View Code
