Binary Exponentiation
Binary exponentiation is a trick that allows us to calculate in instead of .
Resources
I still need to understand, this recursive relationship (Specifically how to deal with these odd powers), but I get the overall idea.
Recursive code
long long binpow(long long a, long long b) {
if (b == 0)
return 1;
long long res = binpow(a, b / 2);
if (b % 2)
return res * res * a;
else
return res * res;
}
You always get the largest power, and you halve it each time.
Iterative version (faster, duh)
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
Modular Exponentiation
This is from CPH The following function calculates the value of :
int modpow(int x, int n, int m) {
if (n == 0) return 1%m;
long long u = modpow(x,n/2,m);
u = (u*u)%m;
if (n%2 == 1) u = (u*x)%m;
return u;
}