¿Cómo resolverías (2 ^ 2 ^ a mod b)?

Considere la representación de 2 ^ x en binario en lugar de decimal. Siempre será 1 y luego algunos ceros. Específicamente, serán ceros “x”. 2 ^ 0 no tiene ceros finales, 2 ^ 1 tiene 1 cero final, etc. Por lo tanto 2 ^ (2 ^ a) tendrá 2 ^ a ceros finales. Esto será útil para el paso del patrón al que haré referencia más adelante.

A partir de ahí, puede dividir por b y tomar el resto. En el caso especial donde b = 2 ^ k, está tomando los últimos k términos de su número anterior. Para todos los demás números, surgirá un patrón en la división que le permitirá calcularlo más rápido que simplemente realizar el paso de división completo si eso fuera de interés. Esto es más rápido para los números donde b es menor que 2 ^ a porque hay un máximo de b posibilidades para el resto de la división (cuando solo hay 0s en la representación numérica como en binario) en el patrón de longitud máxima que luego se repetirá, entonces que cualquier cálculo pasado que al continuar con el cálculo completo se repita y se pueda omitir.

* recuerda volver a convertir a decimal cuando consideres tu respuesta

Una forma sencilla de ver este problema es dividirlo en un subproblema:
2 ^ (2 ^ a) = 2 ^ (2. (2 ^ (a-1))) = 2 ^ (2 ^ (a-1) + 2 ^ (a-1)) = 2 ^ (2 ^ ( a-1)) * 2 ^ (2 ^ (a-1))
Entonces, la solución de f (a) = (2 ^ 2 ^ a) = f (a-1) * f (a-1)
Por lo tanto, F (a) = f (a) mod b = (f (a-1) * f (a-1)) mod b = (f (a-1) mod b * f (a-1) mod b ) mod b = (F (a-1) * F (a-1)) mod b
Caso base F (1) = 4 mod b

La solución se puede encontrar en: HackerRank 101 Hack Diciembre de 2014 Superpoderes de 2