Calculando (a^b)%MOD com grandes expoentes

Neste desafio de codificação, a tarefa é calcular o valor de pow( a, b)%MOD, onde o expoente b pode ser extremamente grande. Embora o método convencional de complexidade de tempo log(b) seja adequado para valores menores, torna-se impraticável quando b excede a capacidade de tipos de dados longos em C.

No entanto, uma abordagem mais eficiente envolve aproveitar a função totiente de Euler, φ(MOD). O teorema de Euler afirma que a^φ(MOD)≡1(mod MOD). Isso significa que a potência de a pode ser significativamente reduzida para a^(b % φ(MOD)).

Calcular φ(MOD) é em si uma tarefa não trivial, mas pode ser alcançada usando métodos de fatoração de inteiros . Uma vez calculado, o expoente b pode ser substituído por b % φ(MOD) para reduzir drasticamente o tempo de cálculo.

Refinamentos adicionais

Em 2008, Schramm demonstrou que φ (b) pode ser obtido a partir da transformada discreta de Fourier de mdc(b, i), para i variando de 1 a b. Isso elimina a necessidade de fatoração explícita.

Além disso, a função de Carmichael, λ(MOD), pode ser usada para obter a resposta correta, especialmente quando a e MOD compartilham fatores comuns.

Implementação de código

O seguinte trecho de código serve como exemplo em C:

#include 
#include 

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }

ll pmod(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b % 2 == 1) {
        return (a * pmod(a, b - 1, mod)) % mod;
    } else {
        ll tmp = pmod(a, b / 2, mod);
        return (tmp * tmp) % mod;
    }
}

int main() {
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout