d506 - 大师求幂题(求幂系列题9)
題目描述
題目要求計算 7 的 86495 次方，並輸出結果。由於結果非常大，無法使用內建的資料型態儲存，因此需要使用字串來表示大數。
解題思路
此題的核心在於處理大數的乘法和冪運算。由於直接計算 7 的 86495 次方會導致溢位，因此採用以下策略：
- 大數表示: 使用字串來表示大數，每個字元代表一個數字。
- 大數乘法: 實作一個大數乘法函數
mul()，將兩個大數字串相乘，並返回結果字串。此函數使用陣列tmp儲存中間結果，並處理進位。 - 快速冪 (Divide and Conquer): 實作一個快速冪函數
bigmod()，利用分治法來計算大數的冪。如果指數t是偶數，則計算base^(t/2)的平方；如果指數t是奇數，則計算base^(t/2)的平方乘以base。 - 記憶化 (Memoization): 使用
map(qk 和 qk2) 來儲存已經計算過的乘法和冪結果，避免重複計算，提高效率。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是指數的大小。快速冪算法將指數分解為 log n 個步驟，每個步驟需要進行一次大數乘法，大數乘法的時間複雜度為 O(n^2)，因此總時間複雜度為 O(n^2 log n)。由於使用了記憶化，實際執行時間會更短。
- 空間複雜度: O(n)，主要用於儲存大數字串和
map中的結果。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,i,k,tmp[73121];
map <string,string> qk;
map <string,string> qk2;
string a;
string toReString(int b){
string rt;
while(b){
rt+=b%10+48;
b/=10;
}
return rt;
}
string mul(string a,string b){
string fd = a+"*"+b;
if(qk.find(fd)!=qk.end())return qk[fd];
int al=a.length(),bl=b.length(),cal=al+bl;
for(int i=0;i<=cal;++i)tmp[i]=0;
for(int i=al-1,it=0;i>=0;--i,++it)
if(a[i]!='0')
for(int j=bl-1,it2=it;j>=0;--j,++it2)
tmp[it2]+=(a[i]-'0')*(b[j]-'0');
int tl=0;
for(int i=0;i<73120;++i){
if(tmp[i])tl=i;
else if(tmp[i]==0&&i>=cal) break;
if(tmp[i]>=10){
tmp[i+1]+=tmp[i]/10;
tmp[i]%=10;
}
}
string rt;
for(int i=tl;i>=0;--i)rt+=tmp[i]+'0';
qk[fd] = qk[b+"*"+a] = rt;
return rt;
}
string bigmod(string base,int t){
if(t==0)return "1";
if(t==1)return base;
string fd=base+'^'+toReString(t);
if(qk2.find(fd)!=qk2.end())return qk2[fd];
string fd2=base+'^'+toReString(t/2);
string tmp2 = bigmod(base,t/2);
qk2[fd2]=tmp2;
string ans;
if(t%2)
qk2[fd] = ans = mul(mul(tmp2,tmp2),base);
else
qk2[fd] = ans = mul(tmp2,tmp2);
return ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cout << bigmod("7",86495);
}