The above power function calculates a^b in O( log(b) ) by using what is called as exponentiation by squaring. The idea is very simple:
(a^2)^(b/2) if b is even and b > 0
a^b = a*(a^2)^((b-1)/2) if b is odd
1 if b = 0
This idea can be implemented very easily as shown below:
/* This function calculates (a^b)%c */
int modulo(int a,int b,int c)
{
long long x=1,y=a;
while(b > 0)
{
if(b%2 == 1)
{
x=(x*y)%c;
}
y = (y*y)%c; // squaring the base
b /= 2;
}
return x%c;
}
The above power function is just a recursive way of doing this.
and as you asked about this
but it will be of great help if anyone explains the mathematics behind using return(base*Power(base,expo-1)%mod)
this is the same as checking if expo is odd then multiplying base with base^(expo-1) so that the new expo i.e. (expo-1) will become even and repeated squaring can be done
For more info refer:
Topcoder Tutorial
wiki: expo by squaring