Rechnen modulo einer Primzahl
Addieren und multiplizieren Sie innerhalb des Moduls
Rechnen modulo einer Primzahl ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum das Modulo nehmen
Ergebnisse in Programmierwettbewerben können riesig werden, weit über jeden Ganzzahltyp hinaus. Deshalb verlangen Aufgaben das Ergebnis modulo einer großen Primzahl, damit die Zahlen klein bleiben. 🔢
Das berühmte Modulo
Die Primzahl, die Ihnen am häufigsten begegnen wird, ist 1000000007, oft als 1e9+7 geschrieben. Sie ist groß genug, um Kollisionen zu vermeiden, und klein genug, um in 64 Bit zu passen.
MOD = 1000000007Was Modulo bedeutet
Der Modulo-Operator liefert den Rest nach einer Division. Daher ist 17 % 5 gleich 2, weil bei der Division von 17 durch 5 ein Rest von 2 bleibt.
print(17 % 5) # 2Addition bleibt innerhalb des Moduls
Sie können zuerst addieren und das Modulo am Ende nehmen oder währenddessen. Der Rest ist in beiden Fällen gleich. Reduzieren Sie daher regelmäßig, damit die Zahlen klein bleiben.
total = (a + b) % MODAuch die Multiplikation bleibt innerhalb des Moduls
Dieselbe Regel gilt für die Multiplikation: Nehmen Sie das Produkt modulo der Primzahl. Python verarbeitet große Ganzzahlen nativ, aber Modulo hält jeden Wert klein und die Berechnung schnell.
prod = (a * b) % MODNach jedem Schritt reduzieren
Wenden Sie in einer langen Schleife in jeder Iteration % MOD an. Dadurch verhindern Sie, dass die Zahlen anwachsen, und halten jede Operation günstig und vorhersehbar.
ans = (ans * i) % MODSubtraktion kann negativ werden
Subtraktion kann in vielen Sprachen einen negativen Rest liefern. Addieren Sie vor dem abschließenden Modulo wieder MOD, damit das Ergebnis im sicheren nichtnegativen Bereich liegt.
diff = (a - b + MOD) % MODPythons praktisches Modulo
Die gute Nachricht: Pythons % liefert bei einem positiven Modulus bereits ein nichtnegatives Ergebnis. Daher ergibt -1 % 7 den Wert 6 und nicht -1, sodass keine Korrektur nötig ist.
print(-1 % 7) # 6Modulo lässt sich auf Operationen verteilen
Die Grundidee: (a op b) % m ist bei Addition und Multiplikation gleich (a%m op b%m) % m. Dadurch können Sie die Eingaben vor dem Kombinieren reduzieren.
Division ist der Knackpunkt
Addition, Subtraktion und Multiplikation funktionieren sauber unter einem Modulo. Eine gewöhnliche Division jedoch nicht, dafür benötigen Sie später in diesem Kurs ein modulares Inverses.
MOD am Anfang einmal festlegen
Definieren Sie MOD am Anfang Ihrer Lösung als Konstante. Ein einziger benannter Wert ist besser, als 1000000007 im Code zu verstreuen, wo sich ein Tippfehler leicht verstecken kann.
MOD = 10**9 + 7Schnelltest
Warum addieren Sie vor dem Modulo einer Subtraktion MOD?
Rückblick
Sie halten riesige Anzahlen nun mit einem Primzahlmodul wie 1e9+7 klein. Reduzieren Sie Addition, Subtraktion und Multiplikation bei jedem Schritt, achten Sie auf negative Werte und verwenden Sie für Division Inverse. 🎯
Häufig gestellte Fragen
Ist die Lektion „Rechnen modulo einer Primzahl“ kostenlos?
Ja — der vollständige Text von „Rechnen modulo einer Primzahl“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Rechnen modulo einer Primzahl“?
Addieren und multiplizieren Sie innerhalb des Moduls Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Rechnen modulo einer Primzahl“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Rechnen modulo einer Primzahl
- Schnelle modulare Exponentiation
- Modulares Inverses mit Fermat
- nCr mit vorberechneten Fakultäten