快速冪

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

(資料圖片)

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

前引

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

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

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

正文

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

a^b= 1 !b

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

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

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

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

不過(guò)因?yàn)檫f歸本身有開(kāi)銷(xiāo)，所以一般把遞歸式的寫(xiě)法改成非遞歸式的，以實(shí)現(xiàn)這種思路、算法本應(yīng)有的優(yōu)秀效率。（優(yōu)化）

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

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

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