一個引子

如何求得a的b次冪呢，那還不簡單，一個for循環就可以實現！

void main(void) {int a, b;int ans = 1;cin >> a >> b;for (int i = 1; i <= b; i++){ans *= a;}cout << ans; }

那么如何快速的求得a的b次冪呢？上面的代碼還可以優化嗎？

當然是ok的！下面就介紹一種方法-二分求冪。

二分求冪

所謂二分求冪，即是將b次冪用二進制表示，當二進制位k位為1時，需要累乘a的2^k次方。

下面優化一下上面的代碼：

void main(void) {int a, b;int ans = 1;cin >> a >> b;while (b != 0){//當二進制位k位為1時，需要累乘a的2^k次方，然后用ans保存if (b % 2 == 1){ans *= a;}a *= a;//每次除以2，轉換成二進制位b /= 2;}cout << ans; }

舉個例子，當b = 5時，b的二進制為101。

循環次數	二進制位	ans值	a值	b值
0	101	1	a	5
1	101	2	a2	2
2	101	2	a4	1
3	101	32	a16	0

從上表我們可以直觀的看出5次冪就可以轉換為(2^0+2^2)，即a的5次冪就轉變為a的(2^0+2^2)次冪，即a的2^0與a的2^2的乘積。

再來個例子-鞏固

此題來源于九度教程“人見人愛A^B”。

題目描述：

求A^B的最后三位數表示的整數。

輸入：

輸入數據包含多個測試實例，每個實例占一行，由兩個正整數a和b組成，其中（1<=a,b<=10000），如果a = 0，被= 0，則表示輸入數據結束，不做處理。

輸出：

對于每個測試實例，輸出a^b的最后三位表示的整數，每個輸出占一行。

樣例輸入：

2 3

12 6

6789 10000

0 0

樣例輸出：

8

984

1

對于這道題，完全可以用上面的二分求解方法，可以仿照上面的代碼進行實現。但是有一點需要注意的是，我們不肯能定義一個整型變量或者long long類型的變量取保存如樣例給出的數據a = 6789,b=10000，a^b的計算結果。因為數字太龐大了，在整數范圍內是無法表示的。所以我們可以只保存每次計算結果的后三位，因為最終結果的后三位取決于其中間值的后三位。

好吧，給出代碼：

void main(void) {int a, b;while ((cin >> a >> b)){int ans = 1;if (a == 0 && b == 0)break;while (b != 0){//當二進制位k位為1時，就累加a的2^k次方if (b % 2 == 1){ans *= a;ans %= 1000;}a *= a;a %= 1000;//每次除以2，轉換成二進制位b /= 2;}cout << ans;}}

?

總結

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

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