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}}$. Em seguida, $a^k$ pode ser expresso como um produto dessas potências pré-calculadas. Isso é possível porque qualquer inteiro $k$ pode ser representado em sua forma binária, onde cada bit corresponde a uma potência de 2. Se o $i$-ésimo bit (a partir de 0) for 1, então $2^i$ faz parte da soma que compõe $k$. Assim, $a^k = a^{\sum_{i \in \text{bits_set}(k)} 2^i} = \prod_{i \in \text{bits_set}(k)} a^{2^i}$.

Implementação Para construir $a^k$, iteramos sobre os bits de $k$ da direita para a esquerda (do menos significtaivo para o mais significativo). Mantemos uma variável para o resultado acumulado (inicializada em 1) e uma variável para a potência atual de $a$ (inicializada em $a$).

Se o bit atual de $k$ for 1, multiplicamos o resultado acumulado pela potência atual de $a$. Em cada passo, a potência atual de $a$ é elevada ao quadrado (representando o avanço para o próximo bit, que tem valor dobrado) e $k$ é deslocado para a direita (para processar o próximo bit).

Considere calcular $a^5$. A representação binária de 5 é $101$.

1. Bit 0 (mais à direita): É 1. O resultado acumulado é multiplicado por $a^{2^0} = a$. A potência atual se torna $a^2$. $k$ se torna $10_2$ (2).
2. Bit 1: É 0. O resultado acumulado permanece o mesmo. A potência atual se torna $(a^2)^2 = a^4$. $k$ se torna $1_2$ (1).
3. Bit 2: É 1. O resultado acumulado é multiplicado por $a^4$. A potência atual se torna $(a^4)^2 = a^8$. $k$ se torna $0_2$ (0).

O loop termina. O resultado acumulado é $a \cdot a^4 = a^5$.

A lógica do algoritmo é: Enquanto $k > 0$: Se o último bit de $k$ for 1, multiplique o resultado pelo valor da potência atual. Eleve ao quadrado o valor da potência atual. Desloque $k$ para a direita em um bit.

Considerações de Overflow É crucial usar tipos de dados de 64 bits (long long em C++) para as variáveis que podem exceder o limite de inteiros de 32 bits, como o resultado acumulado e a potência atual. Todas as operações de multiplicação intermediárias devem aplicar o módulo $p$ para evitar overflow e garantir a correção do resultado.

Código para Exponenciação Rápida

#include <iostream>

typedef long long ll;

// Calcula (a^b) % p
ll power(int base, int exp, int mod) {
    ll res = 1 % mod;
    ll current_power = base % mod; // Use long long para a base também

    while (exp > 0) {
        if (exp % 2 == 1) { // Verifica o último bit
            res = (res * current_power) % mod;
        }
        current_power = (current_power * current_power) % mod; // Eleva ao quadrado
        exp /= 2; // Desloca para a direita
    }
    return res;
}

int main() {
    int n;
    std::scanf("%d", &n);
    
    while (n--) {
        int a, b, p;
        std::scanf("%d%d%d", &a, &b, &p);
        std::printf("%lld\n", power(a, b, p));
    }
    
    return 0;
}

Cálculo de Inverso Multiplicativo usando Epxonenciação Rápida

Teorema de Euler e Pequeno Teorema de Fermat

• Teorema de Euler: Se $a$ e $p$ são coprimos (ou seja, $\gcd(a, p) = 1$), então $a^{\phi(p)} \equiv 1 \pmod{p}$, onde $\phi(p)$ é a função totiente de Euler.
• Pequeno Teorema de Fermat: Se $p$ é um número primo, então para qualquer inteiro $a$ não divisível por $p$, temos $a^{p-1} \equiv 1 \pmod{p}$. Dois números são coprimos se o único divisor comum positivo entre eles é 1.

Abordagem Este problema assume que $p$ é sempre um número primo. Portanto, podemos usar o Pequeno Teorema de Fermat para encontrar o inverso multiplicativo.

O inverso multiplicativo de $b$ módulo $m$ é um número $x$ tal que $b \cdot x \equiv 1 \pmod{m}$. Se $b$ e $m$ são coprimos, então tal inverso existe. Pelo Pequeno Teorema de Fermat, se $p$ é primo e $b$ não é um múltiplo de $p$, temos $b^{p-1} \equiv 1 \pmod{p}$. Podemos reescrever isso como $b \cdot b^{p-2} \equiv 1 \pmod{p}$. Comparando com a definição de inverso multiplicativo ($b \cdot x \equiv 1 \pmod{p}$), concluímos que $x = b^{p-2}$.

Portanto, para encontrar o inverso multiplicativo de $a$ módulo $p$ (onde $p$ é primo), calculamos $a^{p-2} \pmod{p}$ usando a exponenciação rápida.

Há duas condições importantes:

1. Se $a$ e $p$ são coprimos, o inverso existe e é $a^{p-2} \pmod{p}$.
2. Se $a$ e $p$ não são coprimos, o inverso não existe. Como $p$ é primo, isso ocorre apenas se $a$ for um múltiplo de $p$ (ou seja, $a \equiv 0 \pmod{p}$).

Código para Inverso Multiplicativo

#include <iostream>

typedef long long ll;

// Calcula (base^exp) % mod
ll power(int base, int exp, int mod) {
    ll res = 1;
    ll current_power = base % mod;

    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (res * current_power) % mod;
        }
        current_power = (current_power * current_power) % mod;
        exp /= 2;
    }
    
    return res;
}

int main() {
    int n;
    std::scanf("%d", &n);
    while (n--) {
        int a, p;
        std::scanf("%d%d", &a, &p);
        // Se p é primo, a e p são coprimos a menos que a seja múltiplo de p.
        if (a % p == 0) {
            puts("impossible"); 
        } else {
            // O inverso de a mod p é a^(p-2) mod p pelo Pequeno Teorema de Fermat.
            printf("%lld\n", power(a, p - 2, p));
        }
    }
    return 0;
}