Calculer modulo un nombre premier
Additionner et multiplier tout en restant modulo la valeur donnée
Calculer modulo un nombre premier est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Pourquoi utiliser le modulo
Les réponses des concours peuvent devenir énormes, bien au-delà de la capacité de n’importe quel type entier utilisé ailleurs. Les problèmes demandent donc le résultat modulo un grand nombre premier afin de garder des nombres de petite taille. 🔢
Découvrez le modulo célèbre
Le nombre premier que vous rencontrerez le plus souvent est 1000000007, souvent écrit 1e9+7. Il est juste assez grand pour éviter les collisions et suffisamment petit pour tenir sur 64 bits.
MOD = 1000000007Signification du modulo
L’opérateur modulo donne le reste d’une division. Ainsi, 17 % 5 vaut 2, car 17 laisse un reste de 2 lorsqu’il est divisé par 5.
print(17 % 5) # 2L’addition reste dans le modulo
Vous pouvez d’abord additionner, puis prendre le modulo à la fin, ou le prendre au fur et à mesure. Le reste est le même dans les deux cas : réduisez donc souvent les nombres pour les garder petits.
total = (a + b) % MODLa multiplication aussi
La même règle s’applique à la multiplication : prenez le produit modulo le nombre premier. Python gère nativement les entiers de grande taille, mais prendre le modulo garde chaque valeur petite et accélère les calculs.
prod = (a * b) % MODRéduire après chaque étape
Dans une longue boucle, appliquez % MOD à chaque itération. Cela empêche les nombres d’exploser et maintient chaque opération rapide et prévisible.
ans = (ans * i) % MODLa soustraction peut devenir négative
La soustraction peut produire un reste négatif dans de nombreux langages. Ajoutez de nouveau MOD avant le modulo final afin que le résultat se trouve dans l’intervalle sûr commençant à 0.
diff = (a - b + MOD) % MODLe modulo convivial de Python
Bonne nouvelle : l’opérateur % de Python renvoie déjà un résultat non négatif lorsque le modulo est positif. Ainsi, -1 % 7 vaut 6 et non -1, ce qui vous évite une correction supplémentaire.
print(-1 % 7) # 6Le modulo se distribue sur les opérations
L’idée essentielle est la suivante : (a op b) % m est égal à (a%m op b%m) % m pour l’addition et la multiplication. Vous pouvez donc réduire les entrées avant de les combiner.
La division est l’exception
L’addition, la soustraction et la multiplication fonctionnent correctement avec un modulo. En revanche, la division ordinaire ne fonctionne pas ainsi : vous aurez besoin plus tard dans ce cours d’un inverse modulaire.
Définir MOD une seule fois au début
Définissez MOD comme une constante au début de votre solution. Une valeur nommée vaut mieux que de disperser 1000000007 dans le code, où une faute de frappe pourrait passer inaperçue.
MOD = 10**9 + 7Vérification rapide
Pourquoi ajouter MOD avant de prendre le modulo d’une soustraction ?
Récapitulatif
Vous savez maintenant garder de grands nombres de combinaisons sous contrôle grâce à un modulo premier comme 1e9+7. Réduisez l’addition, la soustraction et la multiplication à chaque étape, faites attention aux valeurs négatives et réservez la division aux inverses. 🎯
Questions Fréquemment Posées
La leçon « Calculer modulo un nombre premier » est-elle gratuite ?
Oui — le texte complet de « Calculer modulo un nombre premier » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Calculer modulo un nombre premier » ?
Additionner et multiplier tout en restant modulo la valeur donnée Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Calculer modulo un nombre premier » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Calculer modulo un nombre premier
- Exponentiation modulaire rapide
- Inverse modulaire par Fermat
- nCr avec des factorielles précalculées