← OlimpiApp
Olimpico
Informatica · Algoritmi
Massimo numero di moltiplicazioni per e fino a 300
Il seguente pseudocodice calcola $a^{b}$ con l'esponenziazione veloce (square-and-multiply):
function power(a, b):
result = 1
while b > 0:
if b is odd:
result = result * a
a = a * a
b = b // 2
return resultConsidera ogni istruzione result = result * a oppure a = a * a effettivamente eseguita come una moltiplicazione, e indica con $m(e)$ il numero totale di moltiplicazioni eseguite quando $b=e$.
Qual è il valore massimo possibile di $m(e)$ al variare di $e$ con $1 \le e \le 300$?