Exponenciación rápida (modular)

Tema: Matemática y Combinatoria · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 10 de la Ruta de Aprendizaje.

Qué hace

Calcula b^e (mód m) en O(log e) elevando al cuadrado repetidamente.

Complejidad: O(log e).

Cuándo usarlo

Potencias modulares grandes; multiplicar muchas veces; base de muchas fórmulas de conteo módulo p.

Implementación recomendada (C++)

long long power(long long b, long long e, long long mod) {
    long long r = 1 % mod; b %= mod;
    while (e > 0) {
        if (e % 2 == 1) r = r * b % mod;   // exponente impar: multiplica una vez
        b = b * b % mod;                   // cuadrado en cada paso
        e /= 2;                            // y la mitad del exponente
    }
    return r;
}

⚠️ Notas

Es exactamente el código del módulo 10 de la Ruta de Aprendizaje. Si mod supera ~3·10^9, el producto se sale de long long: multiplica con (__int128)r * b % mod. Ojo: el inverso modular (b^(p-2)) está fuera del syllabus — ver Syllabus IOI.