快速冪詳解（通俗易懂！）

本文爲博主原創文章，未經允許不得轉載。如有問題，歡迎指正！

快速冪詳解

問題背景：
粗暴求解：
如何解決超時問題：
如何解決乘法溢位的問題：
AC完整程式碼
總結：

（一）一些說明
（二）特殊情況&程式碼模板：

問題背景：

題目描述：
求 a 的 b 次方對 p 取模的值，其中 0≤a,b,p≤10⁹ 。
輸入描述:
三個用空格隔開的整數a,b和p。
輸出描述:
一個整數，表示a^b mod p的值。
範例1
輸入
2 3 9
輸出
8
來源：牛客網
題目鏈接：https://ac.nowcoder.com/acm/contest/996/A

粗暴求解：

不考慮數據範圍，我們可以很容易想到以下的解法：

typedef long long LL;
LL POW(LL a,LL b,LL p){
LL res=1;
while(b){
res=res*a;
b--;
}
return  res%p;
}

看了題目的數據範圍，發現這個演算法會出現以下兩個問題：
1. 程式超時。（b的值達到了10⁹）
2. 乘法溢位。（res在累乘的時候可能太大）

如何解決超時問題：

1.超時原因：指數b過大、累乘的次數過多。故應該從指數b出發，降低累乘的次數。
2.我們知道任何一個正整數都可以由2的整數次冪相加得到。例如:
7=1+2+4 ，9=1+8 ，11=1+2+8，12=4+8，21=1+4+16。
3.令a的初始值爲A，將a的值不斷和自身相乘並不斷賦給自身，那麼A的指數也恰好爲2的整數次冪。具體的迭代過程如下：
a=a (初始值) (a==A¹)
a=a*a （a==A²）
a=a*a (a==A⁴)
a=a*a (a==A⁸)
a=a*a (a==A¹⁶)
a=a*a (a==A³²)
4.由(a^m) *(a ⁿ)=a^(m+n) 可知，在以上的迭代過程中選擇一些固定的a值和res進行累乘，就可以使得res等於A^b次方。
5.那麼要選擇哪幾次迭代的a值進行累乘呢？我們把b轉化成二進制表示，就可以直觀地看到b是由哪些2的整數次冪相加得到。例如b等於11，其二進制爲(1011)₂。故11=2⁰ +2¹ +2³ =1+2+8。A¹¹ =(A¹)*(A²)*(A⁸) =A^(1+2+8) ，即選擇A¹ 、A² 、A⁸ 進行累乘可以得到A¹¹。
6.判斷b&1是否爲1可以檢測b的二進制的最後一位是否是1。不斷將b右移就可以檢測b的每一位。
7.檢測b在二進制表示下的每一位，若當前位是1，就把當前的迭代值a累乘。
8.回圈由b- -改爲b=b>>1,時間複雜度變爲爲log₂b。

計算a^45的過程模擬：

在这里插入图片描述

具體程式碼如下（記爲程式碼一）：

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1;
while(b){       
if（b&1）res=res*a;     / /若b&1==1，就選擇當前的迭代值a和res累乘。
a=a*a;                  / /迭代構造a,a是初始值的2的整數次冪
b=b>>1;                / /將b右移一位
}                   / /以上計算得到a^b
return res%p;      / /取模
}

此做法降低了時間複雜度，但並沒有解決溢位的問題。

如何解決乘法溢位的問題：

首先引入一個模運算的規律：(a * b) % p = (a % p * b % p) % p 。還可以推廣到任意多個因數因數相乘再取模：(a*b*c)%d=(a%d*b%d*c%d)%d。即任意多個因數相乘再取模等於各因數取模後的乘積再取模。對於上面優化過後的程式碼，只需每一步都對因數（a*a）取模，同時對「各因數取模後的乘積」res*a再取模,即可維持模值的正確性。由於每一步都取模，累乘後的值就不會溢位了。（注意符號*和符號%的優先順序一樣，故從左到右計算表達式）。
具體程式碼如下（記爲程式碼二）：

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1;
while(b){       
if（b&1）res=res*a%p;     / /對「各因數取模後的乘積」res*a再取模
a=a*a%p;                 / /對因數(a*a)取模
b=b>>1;                  
}                  
return res;     
}

AC完整程式碼

#include<iostream>
using namespace std;
typedef long long LL;
LL POW(LL a,LL b,LL p){
 LL res=1%p;  / /應對b=0而p=1的情況特殊情況
 while(b>0){
 if(b&1)  res=res*a%p;
 a=a*a%p;
 b=b>>1;    
 }   
 return res;
}
int main(){
  LL a,b,p;  
  cin>>a>>b>>p;  
  cout<<POW(a,b,p);     
return 0;    
}

總結：

（一）一些說明

嚴格地說，快速冪演算法應該指的是上面解決了時間複雜度的程式碼一，且程式碼返回值是res。快速冪只是快速求a^b。（字面上應該要這樣理解才合理吧）。即快速冪演算法程式碼如下。

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1;
while(b){       
if（b&1）res=res*a;     / /若b&1==1，就選擇當前的迭代值a和res累乘。
a=a*a;                  / /迭代構造a,a是初始值的2的整數次冪
b=b>>1;                / /將b右移一位
}                   / /以上計算得到a^b
return res;      / /取模
}

至於程式碼二，應該叫「快速冪取模演算法」更合理吧。我覺得只有把兩者區分一下，逐個弄懂，纔不至於搞懵了。（很多資料都是直接上最終程式碼二，使得「求冪」和「取模」冗雜在一起，沒有遞進的邏輯分析，不容易理解）。

（二）特殊情況&程式碼模板：

在一些oj上，題目的測試數據可能會是b=0,而p=1的情況（此時res應該爲0）。如果按上面的程式碼二，while回圈沒有執行則會返回錯誤值1。

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1%p;     / /應對b=0而p=1的情況
while(b){       
if（b&1）res=res*a%p;     / /對「各因數取模後的乘積」res*a再取模
a=a*a%p;                 / /對因數(a*a)取模
b=b>>1;                  
}                  
return res;     
}