d462 - 幸运的朋友(求幂系列题6)
題目描述
題目要求計算一個數字 a 的 n 次方，然後輸出結果從第 i 位開始連續 k 位數。如果 a 的 n 次方位數不足 k 位，則輸出所有位數。
解題思路
這題的核心在於高精度計算 a 的 n 次方。由於 a 和 n 的範圍較大，直接使用內建的次方運算可能會導致溢位。因此，需要使用高精度算法來計算次方。程式碼中使用了字符串來表示大數，並實現了字符串乘法運算。
程式碼使用了快速冪算法來加速次方計算。快速冪算法通過將指數分解為二進制表示，並利用平方運算來減少乘法次數，從而提高計算效率。
此外，程式碼還使用了 map 來儲存已經計算過的乘法結果，避免重複計算，進一步優化了性能。
複雜度分析
- 時間複雜度: O(n * log(n) * m^2)，其中 n 是指數，m 是數字的位數。快速冪算法的時間複雜度為 O(log(n))，每次乘法運算的時間複雜度為 O(m^2)，因此總時間複雜度為 O(n * log(n) * m^2)。
- 空間複雜度: O(m^2)，主要用於儲存高精度乘法運算的臨時結果和
map中儲存的乘法結果。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,i,k,tmp[20021];
map <string,string> qk;
string a;
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<20020;++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 tmp2 = bigmod(base,t/2);
if(t%2)return mul(mul(tmp2,tmp2),base);
return mul(tmp2,tmp2);
}
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";
}
}