d467 - 幸运与不幸(求幂系列题8)
題目描述
題目要求計算一個大整數 a 的 n 次方，然後輸出從第 i 位開始連續 k 位數。由於 a 和 n 的大小可能導致結果非常大，因此需要使用大整數運算。
解題思路
由於題目中 a 的範圍較大，直接計算 a^n 會導致整數溢出。因此，需要使用字符串來表示大整數，並實現大整數的乘法運算。程式碼中使用了 map 來儲存已經計算過的乘法結果，以避免重複計算，這是一種簡單的記憶化方法。bigmod 函數使用遞迴和分治的思想來計算大整數的冪，同樣利用 map 進行記憶化。最後，從計算得到的 a^n 的字符串表示中提取從第 i 位開始的 k 位數。
複雜度分析
- 時間複雜度: O(n * log(a)^2)，其中 n 是指數，log(a) 是 a 的位數。這是因為
bigmod函數遞迴地計算a^(n/2)，每次遞迴都需要進行一次大整數乘法，而大整數乘法的時間複雜度是 O(log(a)^2)。 - 空間複雜度: O(log(a)^2)，主要用於儲存大整數的字符串表示和記憶化乘法結果的
map。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,i,k,tmp[60021];
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<60020;++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);
while(cin >> a >> n >> i >> k){
string ans=bigmod(a,n);
--i;
k=min(i+k,(int)ans.length());
for(;i<k;++i)cout << ans[i];
cout << "\n";
}
puts("From tomcat6 Fri Mar 15 09:53:56 2013\nTo: world\"\nSubject: \"Hello");
}