Dados tres números x, y y p, calcule (x^y) % p
Ejemplos:
Input: x = 2, y = 3, p = 5 Output: 3 Explanation: 2^3 % 5 = 8 % 5 = 3. Input: x = 2, y = 5, p = 13 Output: 6 Explanation: 2^5 % 13 = 32 % 13 = 6.
El problema con las soluciones anteriores es que puede ocurrir un desbordamiento para un gran valor de n o x. Por lo tanto, la potencia generalmente se evalúa bajo módulo de un gran número.
La multiplicación ingenua es O(n) con un factor constante muy bajo con %m.
La función Pow calcula en tiempo O (log n) en python, pero toma mucho tiempo cuando los números son lo suficientemente grandes si primero calcula el valor de x y y luego lo modifica con p para obtener (x y ) % p evaluado.
# Simple python code that first calls pow() # then applies % operator. a = 2 b = 100 p = (int)(1e9+7) # pow function used with % d = pow(a, b) % p print (d)
Producción:
976371285
Al calcular con módulo de números grandes, el operador (%) toma mucho tiempo, por lo que se usa una Exponenciación Modular Rápida. Python tiene pow(x, e, m) para calcular el módulo, lo que lleva mucho menos tiempo. [Consulte Python Docs para obtener más detalles]
# Fast python code that first calls pow() # then applies % operator a = 2 b = 100 p = (int)(1e9+7) # Using direct fast method to compute # (a ^ b) % p. d = pow(a, b, p) print (d)
Producción:
976371285
El algoritmo de exponenciación modular rápida se ha explicado más brevemente en el enlace