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