Modulararithmetik
In vielen Fällen interessiert uns nicht der absolute Wert einer Berechnung, sondern nur das Ergebnis einer Berechnung modulo
m (also der Rest nach Division durch m).Interessanterweise begegnen wir modularer Arithmetik jeden Tag. Wenn wir auf unsere Uhr schauen, um die aktuelle Stunde zu erfahren, interessiert uns nicht die Zeit seit Jahresbeginn (oder seit dem Urknall), sondern nur die Stunde des Tages. Diese Stunde ist die Anzahl der seit Jahresbeginn vergangenen Stunden modulo
12 oder 24, je nachdem, was uns gerade interessiert. Wenn die Zeit voranschreitet, springt die Uhr von 0 auf 1, dann auf 2, 3, …, bis sie 11 erreicht, um dann wieder auf 0 zurückzuspringen. Dieser Prozess wiederholt sich unendlich oft. Die angezeigten Zahlen liegen immer zwischen 0 und 11. Haben wir eine beliebige Anzahl Stunden h, die seit Anfang des Jahres vergangen sind, können wir die aktuelle Stunde mit h % 12 bestimmen (dem Rest von h bei Division durch 12).
Wenn wir uns die letzte Ziffer einer Zahl anschauen, können wir uns dies wie eine „Uhr“ mit 10 Stundenpunkten (0, 1, 2, …, 9) vorstellen, die alle möglichen Ziffern repräsentieren. Erhöhen wir eine Zahl um 1, so wird auch die letzte Ziffer bis zu 9 erhöht und springt dann bei einem weiteren Plus von 1 auf 0 zurück. Für eine beliebige Zahl
n erhalten wir ihre letzte Ziffer mit n % 10 (dem Rest aus n bei Division durch 10).Wenn wir mit Bits (0 und 1) arbeiten, können wir uns eine „Uhr“ mit nur 2 Stundenpunkten – 0 und 1 – vorstellen. Wenn wir 1 zu 0 addieren, erhalten wir 1. Wenn wir 1 zu 1 addieren, wird wieder 0 daraus. Für eine beliebige Bit-String-Zahl
n ist ihr letztes Bit n % 2 (der Rest von n bei Division durch 2).Damit ist modulare Arithmetik nichts anderes als eine Uhr mit
m Ziffern (wobei m zum Beispiel 12 für Stunden, 10 für Ziffern oder 2 für Bits sein kann). m kann dabei jede beliebige Zahl sein und in manchen Aufgabenbereichen muss das Ergebnis modulo einer großen Primzahl wie berechnet werden. Solch eine Zahl wird oft gewählt, damit die Berechnungen nicht umgangen werden können und korrekt ausgeführt werden.Addition modulo m
Wenn wir zwei Zahlen
a und b addieren, kann uns nur das Ergebnis modulo m interessieren. Beispielsweise, wenn wir die letzte Ziffer der Summe von a und b betrachten, schauen wir nur auf das Ergebnis modulo 10. Wir können die Rechnung aber noch vereinfachen, indem wir zunächst das Ergebnis von a % m und b % m bestimmen (also beispielsweise beide letzten Ziffern) und erst dann addieren und das Ergebnis wieder modulo m nehmen. Das macht die Rechnung deutlich einfacher: res = (a % m + b % m) % m:Subtraktion modulo m
Stellen wir uns die Subtraktion von
b von a modulo m vor, als würden wir die Uhr um b Einheiten zurückdrehen, ausgehend von der Zeit a. Wenn wir die Uhr von 5 um 2 Stunden zurückdrehen, ergibt sich (5 - 2) % 12 = 3. Drehen wir die Uhr aber von 5 um 7 Stunden zurück, erhalten wir (5 - 7) % 12 = -2 % 12 = 10. Auch wenn die zu subtrahenden Zahlen größer als m sind, können wir zunächst deren Modulo m nehmen: (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:In einigen Programmiersprachen (wie Python) ist der Operator
% so implementiert, dass das Ergebnis immer positiv ist. In anderen Sprachen (wie C++) kann das anders sein. In diesen Fällen muss man, falls das Ergebnis negativ ist, m addieren (beispielsweise 12 zu -2 addieren, um 10 zu erhalten). Das bedeutet im Grunde, die Uhr einmal vollständig vorwärts zu drehen, ohne die angezeigte Stunde zu verändern.Multiplikation modulo m
Wenn wir zwei Zahlen modulo
m multiplizieren, können wir das Ergebnis ebenfalls modulo m betrachten. Ist m zum Beispiel 10, entspricht das dem Bestimmen der letzten Ziffer, nachdem wir zwei Zahlen multipliziert haben:Division modulo m
Eine Division ist komplexer als die zuvor genannten Operationen. Beim Betrachten der letzten Ziffer: Wenn wir 28 durch 7 teilen, erhalten wir 4 ⇒ die letzte Ziffer des Ergebnisses ist 4. Wenn wir aber nur die letzte Ziffer von 28 (nämlich 8) und die letzte Ziffer von 7 (nämlich 7) anschauen, ist es schwierig, daraus direkt 4 abzuleiten. Um Division modulo
m zu berechnen, kann man zum Beispiel auf den Satz von Euler zurückgreifen. Eine ausführlichere Erklärung findet sich hier: https://cp-algorithms.com/algebra/module-inverse.htmlAufgabe: Berechne die Potenz modulo m
Es soll berechnet werden, wobei
x, n und m als Eingabe gegeben werden.Eingabe
Die Eingabe enthält drei ganze Zahlen
x, n (1 ≤ n ≤ ) und m (1 ≤ x, m ≤ ).Ausgabe
Das Programm soll das Ergebnis von ausgeben.
Beispiele
Eingabe | Ausgabe |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB