Exponenciación Binaria

## ¿Que es la Exponenciación Binaria? El algoritmo de exponenciación binaria, es una técnica que nos permite resolver en solo $O(logn)$ multiplicaciones la expresión $a^n$, esto mejora notablemente el algoritmo **naive** que realiza $O(n)$ multiplicaciones. En mi experiencia uno de los usos más frecuentes es en la resolución de problemas de combinatoria, aritmética modular, recurrencias y teoria de grafos. Lo considero un algoritmo sencillo y elemental para el arsenal de cualquier programador, y aún más si te encuentras vinculado al mundo de la programación competitiva. ## Algoritmo La idea detras de la exponenciación binaria es darnos cuenta que podemos dividir la expresión $a^n$ en varias multiplicaciones de expresiones reducidas, utilizando la representación binaria del exponente. ### Veamos un ejemplo: $5^{11} = 5^{1011} = 5^8 * 5^2 * 5^1$ En la expresión de la derecha, al ser las bases iguales sumamos los exponentes y obtendriamos la forma inicial. Si tenemos las a lo sumo $\lfloor{log2(n)}\rfloor + 1$ potencias de la base, calculadas podriamos resolver el problema realizando solo esa cantidad de multiplicaciones. Pero, ¿como calculamos esas potencias?, bueno como los exponentes en la siguiente sequencia son potencias en base dos consecutivas nos quedaria: $5^1 = 5$ $5^2 = 5^1 * 5^1$ $5^4 = 5^2 * 5^2$ $5^8 = 5^4 * 5^4$ `Note:` Cada elemento en la sucesión es el cuadrado del anterior. Entonces la solución seria la mutliplicación de todos esos elementos excepto los correspondientes a un cero en la representación binaria del **n** inicial.En este ejemplo ignorariamos a $5^4$. ## Implementación en C++ ``` long long binary_exponentation( long long a, long long n ){ long long result = 1; while( n != 0 ) { // El ultimo bit de n es un 1 if( n % 2 ) result = result * a; // El siguiente valor de a va a ser igual al cuadrado del anterior a = a * a; // Eliminando el ultimo bit de n n >>= 1; } return result; } ``` Ahora el algoritmo para hallar **x** en la siguiente ecuación: $a^n \equiv x \bmod m$ ``` long long modular_exponentation( long long a, long long n, int m ) { long long result = 1; while( n != 0) { if( n % 2 ) result = result * a % m; a = a * a % m; n >>= 1; } return result; } ``` ## Problemas de práctica: [**COJ - Betty and the Modular Exponentiation (fácil)**](https://coj.uci.cu/24h/problem.xhtml?pid=2422) [**COJ - Cómo puedo ir? (medio)**](https://coj.uci.cu/24h/problem.xhtml?pid=3528) [**DMOJ - Secuencia numerada de lápices (medio)**](https://dmoj.uclv.edu.cu/problem/secnum) [**LightOJ - Unlucky Strings (dificil)**](http://lightoj.com/volume_showproblem.php?problem=1268)