【概述】

快速冪就是利用二進制的性質來快速計算底數的 n 次冪，時間復雜度為 O(log?N)， 與樸素的 O(N) 相比效率有了極大的提高。

但有時指數十分大，利用高精來寫可能會超時，此時就需要十進制快速冪。

【求位數公式】

有時僅要求求 2 的 n 次冪的位數，這里有一個神奇的求位數公式：floor(log(2)/log(10)*n+1)

double res=n*log10(2)+1; cout<<int(res)<<endl;

【二進制快速冪】

以求 a 的 b 次方為例

將 b 轉換成二進制數，該二進制數第 i 位的權為：?

例如：

11 的二進制是 1011，即：11 = 23×1 + 22×0 + 21×1 + 2o×1

因此，我們將計算 a11 轉化為計算?

遞歸公式：

可借助位運算來實現：

b & 1 //取 b 二進制的最低位，判斷和?1 是否相同，相同返回 1，否則返回 0，用于判斷奇偶

b>>1 //把 b 的二進制右移一位，即去掉其二進制位的最低位

int quickPow(int a,int b){int res=1;while(b){if(b&1)res*=a;a*=a;b>>=1;}return res; }

【二進制快速冪取模】

所謂二進制快速冪取模，就是計算給出 a，b，m 三個數，快速計算??的值

分析：以求??為例

因此，可遞歸的對 n 進行二進制分解，在進行快速冪運算的同時進行求模。

int powMod(int a, int b, int m){int res=1;while(b){if(b&1)res=(res*a)%m;a=(a*a)%m;b>>=1;}return res; }

【快速乘法的二進制快速冪取模】

當數非常大時，計算 (a*b)%m 使用 long long 也有可能爆精度，此時需要利用快速乘法，將轉乘法為加法，在模擬的同時不斷求模

LL multMod(LL a,LL b,LL m){//res=(a*b)%ma%=m;b%=m;LL res=0;while(b){if(b&1)res=(res+a)%m;a=(a<<=1)%m;b>>=1;}return res%m; } LL powMod(LL a, LL b, LL m){//res=(a^b)%mLL res=1;LL k=a;while(b){if((b&1))res=multMod(res,k,m)%m;k=Mult_Mod(k,k,m)%m;b>>=1;}return res%m; }

【十進制快速冪】

考慮到指數十分大的情況，例如：，此時用 python 或 Java 大數寫二進制快速冪會超時，這個時候就需要用十進制快速冪來解決。

十進制快速冪與二進制快速冪沒有本質區別，只是拆分指數的方法一個是以十進制，一個是以二進制。

例如：

char b[100007]; LL tenthPow(LL a,LL len,LL mod) {LL res=1;while(len>=0){LL cnt=b[len]-'0';LL cur=a;for(int i=1; i<=cnt; i++)res=res*a%mod;for(int i=1; i<10; i++)cur=cur*a%mod;//進位a=cur;res%=mod;len--;}return res; } int main(){LL a,mod;scanf("%lld",&a);scanf("%s",b);//字符串讀入指數scanf("%lld",&mod);LL len=strlen(b);LL res=tenthPow(a,len-1,mod);printf("%lld^%s %% %lld = %lld",a,b,mod,res);return 0; }

【例題】

• 麥森數（洛谷-P1045）(快速冪+高精度)：點擊這里
• 取余運算||快速冪（洛谷-P1226）(快速冪取模)：點擊這里
• Rightmost Digit（HDU-1061）(快速冪取模)：點擊這里
• Leading and Trailing（LightOJ-1282）(快速冪取模+快速冪取高位)：點擊這里
• Pupu（HDU-3003）(公式推導+快速冪取模)：點擊這里
• 歐拉定理（洛谷-P5091）(十進制快速冪)：點擊這里

總結

以上是生活随笔為你收集整理的数论 —— 快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。