Tous les défis
Moyen 0 résolus 0 % de réussite

Exponentiation modulaire

Calculez une base élevée à une puissance, modulo un nombre, grâce à l'exponentiation rapide.

Ce que vous allez apprendre

  • Élever un nombre à une puissance énorme en O(log exponent) étapes
  • Garder chaque valeur intermédiaire réduite pour éviter les dépassements
  • Gérer un exposant 0 et un modulo égal à 1

Problème

Calculez base^exponent mod modulus. L'exposant peut atteindre 10^18, il est donc impossible de multiplier par base autant de fois. Utilisez plutôt l'exponentiation rapide (exponentiation par carrés successifs) : parcourez les chiffres binaires de l'exposant, élevez la base au carré à chaque étape, et multipliez-la dans le résultat quand le chiffre vaut 1. Cela prend environ 60 étapes pour n'importe quel exposant de cet exercice.

Implémentez modular_exponentiation(base, exponent, modulus).

Réduisez base modulo modulus dès le départ, puis après chaque multiplication. Comme modulus ≤ 10^9, le produit de deux valeurs réduites reste inférieur à 10^18 et tient dans un entier signé de 64 bits.

Entrée

base : la base.

exponent : la puissance à laquelle élever la base.

modulus : le nombre par lequel on prend le reste.

Sortie

Renvoyez base^exponent mod modulus, une valeur entre 0 et modulus − 1. Considérez que base^0 vaut 1 pour toute base, y compris 0, donc la réponse pour un exposant 0 est 1 mod modulus.

Contraintes

0 ≤ base ≤ 10^18

0 ≤ exponent ≤ 10^18

1 ≤ modulus ≤ 10^9

Exemples

Exemple 1
Entrée :
base = 3
exponent = 13
modulus = 50

Sortie attendue :
expected = 23
Entrée :
long long base = 3;
long long exponent = 13;
long long modulus = 50;

Sortie attendue :
long long expected = 23;
Entrée :
long base = 3;
long exponent = 13;
long modulus = 50;

Sortie attendue :
long expected = 23;

Explication

3^13 = 1 594 323, et 1 594 323 = 50 × 31 886 + 23, donc la réponse est 23.

Exemple 2
Entrée :
base = 2
exponent = 10
modulus = 1000

Sortie attendue :
expected = 24
Entrée :
long long base = 2;
long long exponent = 10;
long long modulus = 1000;

Sortie attendue :
long long expected = 24;
Entrée :
long base = 2;
long exponent = 10;
long modulus = 1000;

Sortie attendue :
long expected = 24;

Explication

2^10 = 1024, et 1024 mod 1000 = 24.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Examinez l'exposant un chiffre binaire à la fois, en commençant par le plus faible.

Indice 2

Élevez la base au carré à chaque étape et multipliez-la dans le résultat quand le bit courant vaut 1.

Indice 3

Initialisez le résultat à 1 % modulus, pour qu'un modulo égal à 1 donne 0.

Complexité attendue

temps O(log exponent), espace supplémentaire O(1)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.