Directly calculate $$pow(a,b)$$ is $$O(b)$$. It is trivial. We can use repeated squaring to solve it efficiently as $$O(lgb)$$, that is to say, divide $$b$$ into several power of $$2$$. And calculate $$pow(a,2^i)$$ and sum them.

For example, $$a^{11}=a^{2^0}\times a^{2^1}\times a^{2^3}$$.

Sometimes we want to get the modular exponentiation. The solution is based on the formula.

$$((a\ mod\ p)(b\ mod\ p))\ mod\ p=(ab)\ mod\ p$$

#include <bits/stdc++.h>
using namespace std;

int Exponentiation(int a, int b)
{
int res = 1;
while (b > 0)
{
if (b & 1) res = res * a;
b = b >> 1;
a = a * a;
}
return res;
}

int ModularExponentiation(int a, int b, int n)
{
int res = 1;
a = a % n;
while (b > 0)
{
if (b & 1) res = (res*a) % n;
b = b >> 1;
a = (a*a) % n;
}
return res;
}

int main()
{
int a, b, n;
scanf("%d %d %d", &a, &b, &n);
printf("%d\n",Exponentiation(a, b));
printf("%d\n",ModularExponentiation(a, b, n));
system("pause");
return 0;
}


Result:

2 5 13
32
6


### Reference

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.