OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.

==== Enunciado ====

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$.

==== Idea ====

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.

==== Código ====

<code cpp>

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;
        }
    }
}
</code>

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**).

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página