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.