d499 - 高手求幂题(求幂系列题5)
題目描述
題目要求計算 a 的 n 次方，其中 2 ≤ a ≤ 9，2 ≤ n ≤ 1000。由於結果可能非常大，超出標準整數範圍，因此需要使用特殊的方法來處理。
解題思路
由於 a 和 n 的範圍限制，直接計算 a^n 的值可能會導致整數溢出。因此，我們使用一個陣列來模擬大數的運算。陣列的每個元素儲存結果的每一位數字。
程式碼首先初始化一個大小為 2001 的陣列 ans，並將第一位設定為 1。然後，進行 n 次乘法運算。每次乘法，將陣列中的每個元素乘以 a。接著，處理進位。如果某個元素的值大於 9，則將其除以 10 的餘數存儲在當前位置，將商加到下一位。
最後，從陣列的最高有效位開始，輸出所有非零的數字。
複雜度分析
- 時間複雜度: O(n * 2000) (n 是指數，2000 是陣列大小)
- 空間複雜度: O(2000) (陣列
ans的大小)
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int a,b;
while(cin >> a >> b){
int ans[2001]={0},it=2000;
ans[0]=1;
while(b--){
for(int i=0;i<2001;++i){
ans[i]*=a;
}
for(int i=0;i<2000;++i){
if(ans[i]>9){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
}
}
while(ans[it]==0){
--it;
}
for(int i=it;i>=0;--i){
cout << ans[i];
}
cout << "\n";
}
}