Algoritmos e Estruturas de Dados

Exponenciação Binária

Dado 3 números x, n e m, pede-se que seja calculado o resultado de .

Entrada

A única linha da entrada contém 3 inteiros x, n e m (1 ≤ x, n, m ≤ ).

Saída

O programa deve imprimir o resultado da expressão .

Exemplos

Entrada
Saída
2 10 5
4

Explicação

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

Tutorial

Como todos os números podem ser bastante grandes, é necessário usar um algoritmo rápido para garantir um cálculo ágil. A exponenciação binária é uma forma eficiente de calcular potências elevadas de um número. Ela reduz a quantidade de multiplicações necessárias para obter a potência, sendo mais rápida do que o método tradicional de multiplicar repetidamente de 1 até n por x.
 
O algoritmo de exponenciação binária baseia-se na seguinte observação matemática: se temos um número x elevado à potência n, então pode ser representado como:
  • se n for par
  • se n for ímpar
Isto acelera o cálculo porque podemos determinar apenas uma vez e depois multiplicar o resultado por ele próprio. Assim, o algoritmo pode ser estruturado da seguinte forma:
def binpow(x, n, m):
    if n == 0:                        # Caso base: x^0 = 1
        return 1
    if n % 2 == 0:                    # n é par => calcular a metade e multiplicar
        half = binpow(x, n // 2, m)   # calcular a metade
        return (half * half) % m      # res = x^(n/2) * x^(n/2)

    # n é ímpar => res = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
Com a exponenciação binária, a complexidade de tempo é reduzida de para , pois em cada iteração onde n é par, dividimos n por 2. Note que, quando n é ímpar, na iteração seguinte n torna-se par.
Vamos simular o algoritmo em alguns exemplos:
x = 2, n = 10 (ignora-se m para simplificar)
  1. [n = 10] → n % 2 == 0 ⇒ calcular binpow(2, 5)
  1. [n = 5] → n % 2 ≠ 0 ⇒ return 2 * binpow(2, 4)
  1. [n = 4] → n % 2 == 0 ⇒ calcular binpow(2, 2)
  1. [n = 2] → n % 2 == 0 ⇒ calcular binpow(2, 1)
  1. [n = 1] → n % 2 ≠ 0 ⇒ return 2 * binpow(2, 0)
  1. [n = 0] → n == 0 ⇒ return 1
  1. [volta ao n = 1] ⇒ return 2 * 1 = 2
  1. [volta ao n = 2] ⇒ return 2 * 2 = 4
  1. [volta ao n = 4] ⇒ return 4 * 4 = 16
  1. [volta ao n = 5] ⇒ return 2 * 16 ⇒ 32
  1. [volta ao 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