OIA-Wiki

Calcular el resto de $a^b$ en la división por $m$. Acá, el número $b$ puede ser muy grande, y sin embargo la respuesta no, ya que calculamos el resto en la división por $m$.

La idea es aprovechar el hecho de que $a^b = (a^2)^{b/2}$. Vamos a implemente una función recursiva que eleve al cuadrado la base (haciendo simplemente la cuentita) y divida por dos el exponente. El único cuidado que hay que tener es que si $b$ es impar, al hacer $b/2$ estamos agarrando la parte entera de esa división, entonces tenemos que multiplicar por un $a$ más.

int my_pow(int a, int b, int m){
    if(b==0){
        return 1;
    }else{
        if(b%2==0){
            return my_pow(a*a%m, b/2, m)%m;
        }else{
            return (a*my_pow(a*a%m, b/2, m))%m;
        }
    }
}

Si $m$ es grande, tanto como para que $a*a$ se pueda pasar del valor máximo de int, se recomienda usar long long int en esta función, o tener sumo cuidado (se pueden hacer cosas como 1LL*..., es decir, convertir a long long en el momento de un producto y luego al hacer $\%m$ el número vuelve a entrar en int).