當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

c语言库快速幂函数,C语言 - 快速幂 - 迭代法+递归法 - 详细讲解

發布時間：2024/8/23 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了 c语言库快速幂函数,C语言 - 快速幂 - 迭代法+递归法 - 详细讲解小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

快速冪的作用：

解決求 a ^ n 的問題 (n可以大于1e18)，如果用for循環的話，毫無疑問直接炸掉 …… 所以也就用了算法復雜度在 o(log n)的快速冪算法來解決此類問題。

快速冪遞歸法(基于二分思想)：

那么既然要用到二分法那么怎么二分？既然要遞歸那么如何遞歸？

第一個問題如何二分？

就以2 ^ 10 為例，我們可以以指數入手進行二分， 10 是一個偶數，那么二分一下就是 2^5 * 2^5 ，之后 2^5 中 5為奇數那么就讓 2^5 = 2 * 2^4 ，那么就有了2^4 ，那么對于 2^4 就又有了偶數的2 ^ 4進行二分。

初始

二分變化

2^10

2^5 * 2^5

2^5

2 * 2^4

2^4

2^2 * 2^2

2^2

2^1 * 2^1

2^1

2 * 2^0

由可以看出要對指數的偶數和奇數進行區分從而進行拆分，這樣可以大大的增大程序的效率，就把 o(n)的算法化成了o(log n)。

第二個問題如何進行遞歸？

其實很明了可以看出如果想要遞歸，一定也是以指數為參數進行，因為指數是變化而且牽扯到二分，遞歸的出口就是指數為零結束，我們可以把奇數和偶數進行 if 判斷，如果指數為偶數那么就返回 fib(a , b/2 , m)， (其中a為底數，b為指數，m為模)。

遞歸法代碼以及解析如下：

#include

using namespace std;

typedef long long ll;

ll binarypow(ll a,ll b,ll m) {

if(b==0) return 1;//如果b為0，那么a^0=1

//b為奇數，轉換為b-1

if(b%2==1) return a*binarypow(a,b-1,m)%m;//可以把if(b%2==1)該為if(b&1)這樣會更快一點。

else {//b為偶數，轉換為b/2；

ll mul=binarypow(a,b/2,m);

return mul*mul%m;

}

int main() {

ll a,b,m;

cin>>a>>b>>m;

ll result=binarypow(a,b,m);

cout<

return 0;

}

快速冪迭代法：

迭代法要用到一些二進制，以及位計算的思想，

就如2^13 我們依然以指數入手，我們可以把13化為二進制就是 1 1 0 1 我們發現 1 出現在了 3 號位， 2 號位，以及 0 號位。

那么 13 = 2^3 + 2^2 + 2^1 = 8 + 4 + 1 ，那么劃開不就是

2 ^ 13 = 2 ^ 8 * 2 ^ 4 + 2 ^ 1

如果把一個指數這樣進行拆分那么不就可以對

那么問題 1 如何拆分？

問題：如何拆分？

我們可以用 if (b & 1) 判斷指數的末尾是否為 1 (其中b 為指數，末尾為1 說明是奇數，末尾為0說明為偶數)如果為 1 那么就讓一個變量乘以當前的，例如變量：int ans = 1；讓ans * =a(a為底數)，然后每一次都要a^2 (移到下一位)。然后通過b>>=1把指數移到下一位判斷下一位的末尾數是1 ，還是 0 ，然后就這樣進行一步一步的拆分。

文字看不懂的話再加一個表來輔助理解。

b & 1

ans

空

1101

1*a

a^2

110

a^4

a * a^4

a^8

a^5 * a^8

空

迭代法代碼以及解析如下：

#include

using namespace std;

typedef long long ll;

ll binarypow(ll a,ll b,ll m){

ll ans=1;

while(b>0){

if(b&1){//如果b的二進制末尾為1 ，就相當于被選中了。

//就如2^13 ==> 2^(13==>1101)==> 2^(1101) ==> 3 2 0 號為 1 那么被選中 ==> 2^13 = 2^8 * 2^4 * 2^1

ans=ans*a%m;//令ans累積上a

}

a=a*a%m;//令a平方

b>>=1;//將b的二進制右移一位即

}

return ans;

}

int main(){