Algoritmos y Estructuras de Datos

Exponentiación Binaria

Dado 3 números x, n y m, se te pide calcular el resultado de .

Entrada

La única línea de la entrada contiene 3 enteros x, n y m (1 ≤ x, n, m ≤ ).

Salida

El programa debe imprimir el resultado de la expresión .

Ejemplos

Entrada
Salida
2 10 5
4

Explicación

  1. 2^10 = 1024 ⇒ 1024 mod 5 = 4
 

Tutorial

Dado que todos los números son bastante grandes, es necesario emplear un algoritmo rápido para asegurar que sea lo suficientemente eficiente. 1. La exponentiación binaria es una forma eficaz de calcular potencias de valores grandes. Reduce el número de multiplicaciones necesarias para obtener la potencia, lo que la hace más rápida que el método tradicional de iterar desde 1 hasta n y multiplicar cada vez por x.
 
El algoritmo de exponentiación binaria se basa en la siguiente idea matemática: si tenemos un número x elevado a la potencia n, entonces puede expresarse como:
  • si n es par
  • si n es impar
Esto agiliza el proceso, ya que podemos calcular una sola vez y luego multiplicar el resultado por sí mismo. El algoritmo puede verse así:
def binpow(x, n, m):
    if n == 0:                        # Caso base: x^0 = 1
        return 1
    if n % 2 == 0:                    # n es par => calcular la mitad y multiplicar
        half = binpow(x, n // 2, m)   # calcular la mitad
        return (half * half) % m      # res = x^(n/2) * x^(n/2)

    # n es impar => res = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
Con la exponentiación binaria, reducimos la complejidad de tiempo desde hasta , porque se divide n en cada iteración cuando es par. Es importante notar que, en cada operación en la que n es impar, para la siguiente iteración n pasa a ser par.
Veamos cómo se simula el algoritmo en varios valores de entrada:
x = 2, n = 10 (omitimos m para simplificar)
  1. [n = 10] → n % 2 == 0 ⇒ calculate binpow(2, 5)
  1. [n = 5] → n % 2 ≠ 0 ⇒ return 2 * binpow(2, 4)
  1. [n = 4] → n % 2 == 0 ⇒ calculate binpow(2, 2)
  1. [n = 2] → n % 2 == 0 ⇒ calculate binpow(2, 1)
  1. [n = 1] → n % 2 ≠ 0 ⇒ return 2 * binpow(2, 0)
  1. [n = 0] → n == 0 ⇒ return 1
  1. [subiendo a n = 1] ⇒ return 2 * 1 = 2
  1. [subiendo a n = 2] ⇒ return 2 * 2 = 4
  1. [subiendo a n = 4] ⇒ return 4 * 4 = 16
  1. [subiendo a n = 5] ⇒ return 2 * 16 = 32
  1. [subiendo a n = 10] ⇒ return 32 * 32 = 1024
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue