#include <iostream>
#include <cmath>
using namespace std;
long long int pw(long long int a, long long int n)
{
 int sum=a;
 if(n==0){
  return 1;
 }
 for(int i=0; i<(n-1); i++)
 {
  sum*=a;
 }
 return sum;
}

main()
{
string s;
long long int a,n;
long long int d;
while(cin>>a>>s)
{
if(a==0 && s=="0"){
cout<<"All Over.\n";
break;
}
else{
n=0;
for(int i=0; i<s.size(); i++)
{
n+=(s[s.size()-i-1]-48)*pw(10,i);
}
d=pw(a,n);
cout<<d<<'\n';
}
}
}

怎麼解....求救，為什麼我跑出這個奇怪的數字

快速冪解法是什麼意思，上網查都看不懂

您的答案為: -1112319212
正確答案為: 727009963485125396

首先，在您宣告的 pw() 函式裡，sum 這個變數的型態為 int ， int 能容納的範圍為 -2³¹ ~ 2³¹ - 1 ， 不夠容納題目所求的 -2⁶³ ~ 2⁶³ - 1 （會發生溢位(overflow)，因而造成您的答案出現負值）。

改成 long long 即可。

接著，所謂的「快速冪」可從以下性質觀察而出：

已知，a^b × a^c = a^{b + c} ，而任意一正整數皆可表示為二進位數字，如 42₍₁₀₎ = 101010₍₂₎ 

因此我們可以利用這個性質將任意次方之值分解為 2 的冪次之和，例如 10⁴² = 10^{32 + 8 + 2} ，而就可以進一步拆解為 10³² × 10⁸ × 10² 

而因為現在的次方之數值皆為 2 的冪次，因此可以快速地藉由自己乘自己而得到 10 → 10² → 10⁴ → 10⁸ → 10¹⁶ → …… 最後將相應的次方相乘，即可以得到所求。

此即為——「快速冪」。

像是 10⁴²，本來應該要做 41 次的乘法。套用快速冪的技巧，可以將乘法次數縮減到 8 次。次方越大，縮減次數的比率越大。

假設要求某數的 n 次方，一般作法為 n - 1 次乘法運算；而快速冪只需約莫 log₂(n) 次乘法。

以上，希望有幫助到您。