Viết hàm tính P(n)=a^n(n là số nguyên không âm, a là số nguyên dương) (làm theo c++ ạ)=)

Ta có thể tính `a^n` nhanh bằng cách sử dụng đệ quy (phương pháp chia để trị):

`**` Nếu `n = 0` thì kết thúc đệ quy.

`**` Gọi đệ quy:

`-` Nếu `n` lẻ: power(a, n) = a * power(a * a, n>>1)

`-` Nếu `n` chẵn: power(a, n) = power(a * a, n>>1)

Độ phức tạp của thuật toán là O(logn).

$\\$
Code tham khảo:

#include <iostream>

using namespace std;

long long power(long long a, long long n) {
  if (!n) return 1;
  if (n&1) return a * power(a*a, n>>1);
  else return power(a*a, n>>1);
}

int main() {

  int a, n; cin >> a >> n;
  cout << power(a, n);
  
}

$\\$
$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}

#include <iostream>

using namespace std;

int P(int a,int n)
{
    int s=pow(a,n);
    return s;
}

int main() 
{
    int a,n;
    cin>>a>>n;
    cout<<P(a,n);
}