Problema
Calcula base^exponent mod modulus. El exponente puede llegar a 10^18, así que multiplicar por base esa cantidad de veces es imposible. Usa en cambio la exponenciación por cuadrados: recorre los dígitos binarios del exponente, eleva la base al cuadrado en cada paso y multiplícala por el resultado cuando el dígito sea 1. Para cualquier exponente de este problema bastan unos 60 pasos.
Implementa modular_exponentiation(base, exponent, modulus).
Reduce base módulo modulus al principio y después de cada multiplicación. Como modulus ≤ 10^9, el producto de dos valores reducidos es menor que 10^18 y cabe en un entero de 64 bits con signo.
Entrada
base: la base.
exponent: la potencia a la que se eleva la base.
modulus: el número entre el que se calcula el residuo.
Salida
Devuelve base^exponent mod modulus, un valor de 0 a modulus − 1. Considera que base^0 vale 1 para cualquier base, incluido 0, así que la respuesta para el exponente 0 es 1 mod modulus.
Restricciones
0 ≤ base ≤ 10^18
0 ≤ exponent ≤ 10^18
1 ≤ modulus ≤ 10^9
Ejemplos
Entrada:
base = 3
exponent = 13
modulus = 50
Salida esperada:
expected = 23
Entrada:
long long base = 3;
long long exponent = 13;
long long modulus = 50;
Salida esperada:
long long expected = 23;
Entrada:
long base = 3;
long exponent = 13;
long modulus = 50;
Salida esperada:
long expected = 23;
Explicación
3^13 = 1,594,323, y 1,594,323 = 50 × 31,886 + 23, así que la respuesta es 23.
Entrada:
base = 2
exponent = 10
modulus = 1000
Salida esperada:
expected = 24
Entrada:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;
Salida esperada:
long long expected = 24;
Entrada:
long base = 2;
long exponent = 10;
long modulus = 1000;
Salida esperada:
long expected = 24;
Explicación
2^10 = 1024, y 1024 mod 1000 = 24.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Revisa el exponente un dígito binario a la vez, empezando por el menos significativo.
Pista 2
Eleva la base al cuadrado en cada paso y multiplícala por el resultado cuando el bit actual sea 1.
Pista 3
Empieza el resultado en 1 % modulus, para que con módulo 1 se obtenga 0.
Complejidad esperada
tiempo O(log exponent), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.