快速冪

模板題：P1226 【模板】快速冪 | 取余運(yùn)算

(資料圖片)

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

前引

如果直接暴力求解 pow(a, b) % p 顯然是不可取的：先不論時間的花費，其中 pow(a, b) 得到的結(jié)果就很有可能超出了數(shù)據(jù)范圍。那如果利用abmodk=(amodk)(bmodk)mod k 這條性質(zhì)，即每步取余后再相乘，這樣可以規(guī)避數(shù)據(jù)溢出。但時間復(fù)雜度為 O(n)，n 為次數(shù) 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;}

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

正文

分治思想：可以將 B 進(jìn)行二進(jìn)制分解，分解成一個個子任務(wù)再計算:

a^b= 1 !b

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

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

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

//遞歸寫法參考：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;}

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

//非遞歸式寫法（快速冪）：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;}

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

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