Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Exponenciación modular

Calcula la base elevada al exponente, módulo un número, con exponenciación rápida.

Lo que aprenderás

  • Elevar un número a una potencia enorme en O(log exponent) pasos
  • Mantener reducido cada valor intermedio para evitar desbordamientos
  • Manejar el exponente 0 y el módulo 1

Problema

Ver original (inglés)

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.