Algoritmi e Strutture Dati

Esponenziazione binaria

Dati 3 numeri x, n e m, ti viene chiesto di calcolare il risultato di .

Input

L’unica riga di input contiene 3 interi x, n e m (1 ≤ x, n, m ≤ ).

Output

Il programma deve stampare il risultato dell’espressione .

Esempi

Ingresso
Uscita
2 10 5
4

Spiegazione

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

Tutorial

Dal momento che tutti i numeri possono essere molto grandi, è necessario utilizzare un algoritmo veloce per assicurarsi che il calcolo venga eseguito rapidamente. 1. L’esponenziazione binaria è un metodo efficiente per calcolare potenze elevate di un numero. Riduce il numero di moltiplicazioni necessarie per computare la potenza, rendendolo molto più veloce del metodo tradizionale che prevede un ciclo da 1 a n moltiplicando ripetutamente il risultato per x.
 
L’algoritmo di esponenziazione binaria si basa sulla seguente osservazione matematica: se abbiamo un numero x elevato alla n, allora può essere rappresentato come:
  • se n è pari
  • se n è dispari
def binpow(x, n, m):
    if n == 0:                        # Caso base: x^0 = 1
        return 1
    if n % 2 == 0:                    # n è pari => calcola la metà e moltiplica
        half = binpow(x, n // 2, m)   # calcola la metà
        return (half * half) % m      # res = x^(n/2) * x^(n/2)

    # n è dispari => res = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
Grazie all’esponenziazione binaria, la complessità temporale passa da operazioni a , poiché a ogni passo, quando n è pari, la potenza si dimezza. È importante notare che, ogni volta che n risulta dispari, l’iterazione successiva utilizza un n pari.
Di seguito, una simulazione dell’algoritmo con alcuni input:
x = 2, n = 10 (si trascura m per semplicità)
  1. [n = 10] → n % 2 == 0 ⇒ calcola binpow(2, 5)
  1. [n = 5] → n % 2 ≠ 0 ⇒ restituisce 2 * binpow(2, 4)
  1. [n = 4] → n % 2 == 0 ⇒ calcola binpow(2, 2)
  1. [n = 2] → n % 2 == 0 ⇒ calcola binpow(2, 1)
  1. [n = 1] ⇒ n % 2 ≠ 0 ⇒ restituisce 2 * binpow(2, 0)
  1. [n = 0] ⇒ n == 0 ⇒ restituisce 1
  1. [risalendo a n = 1] ⇒ restituisce 2 * 1 = 2
  1. [risalendo a n = 2] ⇒ restituisce 2 * 2 = 4
  1. [risalendo a n = 4] ⇒ restituisce 4 * 4 = 16
  1. [risalendo a n = 5] ⇒ restituisce 2 * 16 = 32
  1. [risalendo a n = 10] ⇒ restituisce 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