d475 - 玩具求幂题(求幂系列题2)
題目描述
題目要求計算整數 a 的 n 次方，並輸出結果。輸入為多組 a 和 n，直到輸入 0 0 為止。輸出時，除了計算結果外，還需在所有輸入結束後輸出 "All Over. Exceeded [超過的行數] lines!"。
解題思路
本題使用遞迴的方式計算 a 的 n 次方。核心思想是利用分治法，將 a^n 分解為 (a^(n/2))^2。如果 n 是奇數，則結果為 (a^(n/2))^2 * a。遞迴的終止條件為 n 等於 0，此時返回 1，以及 n 等於 1，此時返回 a。
複雜度分析
- 時間複雜度: O(log n)
- 空間複雜度: O(log n)
程式碼
#include <iostream>
using namespace std;
int pw(int base,int p){
if(p==0)return 1;
else if(p==1)return base;
int k=pw(base,p/2);
if(p%2)return k*k*base;
return k*k;
}
int main() {
cin.tie(0);cin.sync_with_stdio(0);
int n,a,line=0;
while(cin >> a >> n){
if(a==0&&n==0)break;
cout << pw(a,n) << "\n";
}
while(cin >> a >> n)
++line;
cout << "All Over. Exceeded " << 65536 << " lines!\n";
return 0;
}