d473 - 秒杀求幂题(求幂系列题4)
題目描述
題目要求計算一個整數 a 的 n 次方，並輸出結果。輸入包含多組測試數據，直到輸入為 0 0 時結束。需要注意的是，a 和 n 的範圍較大，需要使用字串來處理。題目還要求輸出多餘的行數。
解題思路
由於 a 和 n 的範圍超過了標準整數型的表示範圍，因此需要使用字串來表示和處理這些數字。程式碼使用以下策略來計算 a 的 n 次方：
- 簡化輸入: 移除字串
a和n前導的非數字字符。 - 快速冪 (Binary Exponentiation): 使用分治法實現快速冪演算法。如果
n是偶數，則計算(a^(n/2))^2；如果n是奇數，則計算a * (a^(n/2))^2。 - 大數乘法: 由於結果可能非常大，程式碼實現了一個字串乘法函數
mul來處理大數的乘法運算。 - 大數除以 2: 程式碼實現了一個字串除以 2 的函數
div2，用於快速冪演算法中的除法運算。 - 處理負數: 檢查
a是否為負數，並根據n的奇偶性來確定結果的符號。
複雜度分析
- 時間複雜度: O(n * log(a) * log(n))，其中 n 是指數，log(a) 和 log(n) 代表大數乘法和除法運算的複雜度。
- 空間複雜度: O(log(a) + log(n))，主要用於儲存大數的字串表示。
程式碼
#include <iostream>
using namespace std;
int tmp[100],count;
string a,n;
void simpfy(){
int al=a.length(),nl=n.length(),ait=0,nit=0;
string ta,tn;
for(int i=0;i<al;++i,++ait)
if(a[i]>'0'&&a[i]<='9')break;
if(ait==al)a="0";
else{
for(int i=ait;i<al;++i)
ta+=a[i];
a=ta;
}
for(int i=0;i<nl;++i,++nit)
if(n[i]>'0'&&n[i]<='9')break;
if(nit==nl)n="0";
else{
for(int i=nit;i<nl;++i)
tn+=n[i];
n=tn;
}
}
string mul(string a,string b){
int al=a.length(),bl=b.length(),cal=al+bl;
for(int i=0;i<100;++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<100;++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';
return rt;
}
string div2(string b){
if(b=="1"||b=="0")return "0";
int buf=0,bl=b.length();
string rt2,rt;
for(int i=0;i<bl;++i){
rt2+=(b[i]-'0'+buf*10)/2+'0';
buf=(b[i])%2;
}
if(rt2[0]=='0')
for(int i=1;i<bl;++i)
rt+=rt2[i];
else
rt=rt2;
return rt;
}
string bigmod(string base,string t){
if(base=="0"||base=="1")return base;
if(t=="0")return "1";
if(t=="1")return base;
string tmp2=div2(t);
string tmp3=bigmod(base,tmp2);
if(t[t.length()-1]%2)return mul(mul(tmp3,tmp3),base);
return mul(tmp3,tmp3);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> a >> n){
if(a=="0"&&n=="0")break;
int ff=0;
if(a[0]=='-')ff=1;
simpfy();
string ans=bigmod(a,n);
if(ff&&n[n.length()-1]%2&&ans!="0")cout << '-';
cout << ans << "\n";
}
while(getline(cin,a)){
++count;
}
cout << "All Over. Exceeded " << count-1 << " lines!";
}