Calcular (a^b)%MOD con exponentes grandes

En este desafío de codificación, la tarea es calcular el valor de pow( a, b)%MOD, donde el exponente b puede ser extremadamente grande. Si bien el método convencional de complejidad temporal log(b) es adecuado para valores más pequeños, resulta poco práctico cuando b excede la capacidad de tipos de datos largos en C.

Sin embargo, un enfoque más eficiente implica aprovechar la función totient de Euler, φ(MOD). El teorema de Euler establece que a^φ(MOD)≡1(mod MOD). Esto significa que la potencia de a se puede reducir significativamente a a^(b % φ(MOD)).

Calcular φ(MOD) no es en sí mismo una tarea trivial, pero se puede lograr utilizando métodos de factorización de enteros. . Una vez calculado, el exponente b se puede reemplazar con b % φ(MOD) para reducir drásticamente el tiempo de cálculo.

Más refinamientos

En 2008, Schramm demostró que φ (b) se puede obtener a partir de la transformada discreta de Fourier de mcd(b, i), para i que va de 1 a b. Esto elimina la necesidad de una factorización explícita.

Además, la función de Carmichael, λ(MOD), se puede utilizar para obtener la respuesta correcta, especialmente cuando a y MOD comparten factores comunes.

Implementación de código

El siguiente fragmento de código sirve como ejemplo en 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