Doido Dev

A operação de exponenciação modular rápida permite calcular $a^k \pmod{p}$ em complexidade de tempo $O(\log k)$. Para múltiplas consultas, a complexidade total é $O(n \cdot \log k)$, onde $1 \leq a, p, k \leq 10^9$. Princípio Básico A ideia fundamantal é pré-calcular potências de $a$ na forma $a^{2^0}, a^{2^1}, a^{2^2}, \dots, a^{2^{\log k}}$. ...