快速冪

模板題：P1226 【模板】快速冪 | 取余運算

(資料圖片)

快速冪是同余的一個延伸：給定三個整數 a, b, p，求 a^bmod p 的值。

前引

如果直接暴力求解 pow(a, b) % p 顯然是不可取的：先不論時間的花費，其中 pow(a, b) 得到的結果就很有可能超出了數據范圍。那如果利用abmodk=(amodk)(bmodk)mod k 這條性質，即每步取余后再相乘，這樣可以規避數據溢出。但時間復雜度為 O(n)，n 為次數 b ，b<2³¹，很明顯會 TLE。

//暴力解法1（**溢出**）：//include int power(int a, int b, int p) {    return pow(a, b) /*問題所在*/ % p;}//暴力解法2（**超時**）：int power(int a, int b, int p) {    int ans = 1;    for (; b--; /*問題所在*/ )    ans = a % p * ans, ans %= p;    return ans;}

這兩種錯誤的代碼邏輯清晰，可暴力求解對于較大的數據則無用武之地。

正文

分治思想：可以將 B 進行二進制分解，分解成一個個子任務再計算:

a^b= 1 !b

a? a^{b - 1}b & 1

a^{b >> 1}?a^{b >> 1}!(b & 1)

快速冪的思想大抵如此：利用分治算法分解，之后在計算的過程中再進行取模運算時，效率便能讓人滿意許多。

//遞歸寫法參考：int qpow(int a, int b, int p) {    if (!b) return 1;    a %= p;    int res = qpow(a, b >> 1, p);    if (b & 1) return (long long)res * res * a % p;    return res * res % p;}

不過因為遞歸本身有開銷，所以一般把遞歸式的寫法改成非遞歸式的，以實現這種思路、算法本應有的優秀效率。（優化）

//非遞歸式寫法（快速冪）：int qpow(int a, int b, int p) {    int ans = 1;    for (; b; b >>= 1, a = (long long)a * a % p)    if (b & 1)    ans = (long long)ans * a % p;    return ans;}

類似于二分：由于每次計算都會把次數（即 b ）減少一半，問題的規模也跟著降低到原來的一般。快速冪的時間復雜度是優秀的 O(log n)。 （底數為2）

快速冪在數論題中還有一些拓展，但都不在相同的討論范圍之內，故此處不作過多介紹。