Incep prin a-l felicita pe Victor, fiind singurul care a trimis o
rezolvare perfecta.
Ce ar trebui invatat din aceasta problema ?
1. (A*B) mod P = (A mod P)*(B mod P)
Aceasta a fost greseala pentru care au fost ratate testele 7,8 si 9.
2. A^p=| A^(p div 2)*A^(p div 2), p par
| A*A^p, p impar
Deci pentru a calcula A^p putem realiza usor o functie recursiva,
de complexitate O(log p).
Complexitatea algoritmului era deci O(log B).
|
|