遞歸快速幂與非遞歸快速幂模闆

 遞歸快速幂

(對大素數取模)

typedef long long ll;
ll Quick_pow(ll a,int n)
{
  if(n == 0)
    return 1;//出口為"a^0=1"
  else if(n % 2 == 1)
    return  Quick_pow(a, n-1)*a;
  else{
    ll temp = Quick_pow(a, n/2);
    return temp*temp;
  }
}      

雖然簡潔，但會産生額外的空間開銷。我們可以把遞歸改寫為循環，來避免對棧空間的大量占用，即非遞歸快速幂

非遞歸快速幂

typedef long long ll;
ll Quick_pow(int a,int n)
{
  int ans = 1;
  while(n)
  {
    if(n&1)
      ans *= a;
    a *= a;
    n >>= 1;
  }
  return ans;
}