d465 - 不幸的你(求幂系列题7)
題目描述
題目要求計算一個大整數 a 的 n 次方，然後輸出從第 i 位開始連續 k 位數的數字。由於 a 和 n 的範圍較大，直接計算 a^n 可能會導致溢出，因此需要使用大整數運算。
解題思路
本題的核心在於處理大整數的冪運算和字串操作。程式碼使用字串來表示大整數，並實現了以下功能：
- 大整數乘法 (
mul函數): 模擬手算乘法，將兩個大整數字串相乘，並返回結果字串。使用map儲存計算過的結果，避免重複計算，實現記憶化。 - 大整數冪運算 (
bigmod函數): 使用分治法計算大整數的冪。如果指數t為偶數，則遞迴計算(base^(t/2))^2；如果指數t為奇數，則遞迴計算(base^(t/2))^2 * base。同樣使用map儲存計算過的結果，避免重複計算。 - 主函數: 讀取輸入
a、n、i和k，計算a^n，然後從第i位開始輸出連續k位數。
複雜度分析
- 時間複雜度: O(n * log(a)^2 + k)，其中 n 是指數，log(a) 是 a 的位數。大整數乘法的時間複雜度是 O(log(a)^2)，大整數冪運算使用分治法，時間複雜度是 O(n * log(a)^2)。輸出 k 位數的時間複雜度是 O(k)。
- 空間複雜度: O(log(a)^2)，主要用於儲存大整數乘法和冪運算過程中產生的臨時字串。
qk和qk2map 儲存中間結果，最壞情況下需要儲存 O(n * log(a)^2) 的字串，但實際情況下，由於記憶化，儲存量會減少。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,i,k,tmp[50021];
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<50020;++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";
}
}