Para calcular 313 harías 3 x 3 x 3 x … x 313 veces.
Sin embargo, con exponentes grandes es muy lento.
El truco para calcular an es usar la representación binaria del exponente
Con esta técnica podemos calcular an en O(log(n)) pues la representación binaria de n tiene ⌊log₂ n⌋ + 1 bits.
13 en binario es 1101₂. Entonces,31101 = 31000 x 3100 x 31= 38 x 34 x 31tiene menos multiplicaciones.
De modo que solo necesitamos una forma rápida de calcular esos digitos. Por suerte un elemento en la secuencia es solo el cuadrado de el elemento previo
31 = 3
310 = 32 = (31)2 = 32 = 9
3100 = 34 = (32)2 = 92 = 81
31000 = 38 = (34)2 = 812 = 6561
Así que para llegar a la respuesta final solo necesitamos multiplicar 3 de ellos (nos saltamos 32 porque ese bit no se encuentra prendido)
313 = 38 x 34 x 31
= 6561 x 81 x 3
= 1 594 323
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;
}
Módulo m
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1) {
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
return res;
}