L'arithmétique modulaire
Dans de nombreux cas, la valeur absolue d’un calcul ne nous intéresse pas vraiment : ce qui compte, c’est plutôt le résultat de ce calcul modulo
m (c’est-à-dire le reste obtenu après division par m).Fait intéressant, nous utilisons déjà l’arithmétique modulaire au quotidien. Lorsque nous regardons l’heure sur une montre, nous ne cherchons pas le temps écoulé depuis le début de l’année (ou depuis le Big Bang), mais uniquement l’heure courante. Autrement dit, le nombre d’heures écoulées depuis le début de l’année modulo
12 ou 24, selon le format choisi. Au fur et à mesure que le temps avance, l’affichage passe de 0 à 1, puis à 2, 3, … jusqu’à 11, avant de revenir à 0. Ce cycle se répète à l’infini, et les nombres restent toujours compris entre 0 et 11. Si l’on connaît un nombre arbitraire d’heures écoulées h, l’heure en cours se calcule par h % 12 (le reste de la division de h par 12).
Lorsque l’on s’intéresse au dernier chiffre d’un nombre, on peut le voir comme un « cadran » qui possède 10 positions - 0, 1, 2, …, 9, représentant tous les chiffres possibles. À chaque fois qu’on ajoute 1 à un nombre, son dernier chiffre augmente de 1, jusqu’à 9, puis il repasse à 0. Pour un nombre arbitraire
n, on peut obtenir son dernier chiffre par n % 10 (le reste de la division de n par 10).Si l’on travaille avec des bits (0 et 1), on peut imaginer un « cadran » qui ne possède que 2 positions : 0 et 1. Si on ajoute 1 à 0, on obtient 1 ; si on ajoute 1 à 1, on repasse à 0. Pour un nombre binaire arbitraire
n, on peut extraire son dernier bit par n % 2 (le reste de la division de n par 2).Ainsi, l’arithmétique modulaire n’est rien de plus qu’un cadran ayant
m positions (par exemple, m = 12 pour les heures, m = 10 pour les chiffres et m = 2 pour les bits). Le nombre m peut être quelconque et, dans certains problèmes, il faut calculer un résultat modulo un grand nombre premier comme . Ce choix de nombre vise généralement à s’assurer que les calculs ne puissent pas être simplifiés ou évités et qu’ils soient réalisés correctement.Addition modulo m
Lorsqu’on additionne deux nombres
a et b, il se peut qu’on ne s’intéresse qu’au résultat modulo m. Par exemple, pour n’en retenir que le dernier chiffre, on regardera le résultat modulo 10. Cependant, on peut simplifier les calculs en prenant d’abord a modulo m, puis b modulo m, avant d’additionner ces deux résultats et de reprendre à nouveau le modulo. Cela se traduit en code par res = (a % m + b % m) % m :Soustraction modulo m
On peut voir la soustraction de
b à partir de a (toujours modulo m) comme le fait de reculer l’aiguille d’une horloge de b unités en partant de a. Par exemple, reculer l’horloge de 2 heures en partant de 5 donne (5 - 2) % 12 = 3, et reculer l’horloge de 7 heures en partant de 5 donne (5 - 7) % 12 = -2 % 12 = 10. On peut également soustraire des nombres plus grands que m en prenant leur valeur modulo m au préalable : (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3 :Dans certains langages (comme Python), l’opérateur de reste
% renvoie toujours un résultat positif. Dans d’autres (par exemple en C++), ce n’est pas forcément le cas. Par conséquent, dans ces langages, il peut être nécessaire d’ajouter m au résultat final s’il est négatif (ajouter 12 à -2 pour obtenir 10). Intuitivement, cela revient à avancer l’horloge d’une journée complète (ce qui ne modifie pas l’heure affichée).Multiplication modulo m
Lorsqu’on multiplie deux nombres modulo
m, on peut également prendre le résultat final modulo m. Si m vaut 10, il s’agit simplement de déterminer le dernier chiffre du produit de deux nombres :Division modulo m
La division est plus délicate que les autres opérations. Revenons à l’exemple du dernier chiffre. Si l’on divise 28 par 7, on obtient 4 — le dernier chiffre du résultat est alors 4. Mais en prenant simplement le dernier chiffre de 28 (8) et celui de 7 (7), il n’est pas évident de parvenir à 4. Il est possible de réaliser une division modulo
m en utilisant le théorème d’Euler. Une explication plus détaillée est disponible ici : https://cp-algorithms.com/algebra/module-inverse.htmlDéfi : Calculer une puissance modulo m
On vous demande de calculer la valeur de , où
x, n et m sont fournis en entrée.Entrée
L’entrée contient trois entiers
x, n (1 ≤ n ≤ ), et m (1 ≤ x, m ≤ ).Sortie
Le programme doit afficher le résultat de .
Exemples
Input | Output |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB