Problem
Berechne base^exponent mod modulus. Der Exponent kann bis zu 10^18 groß sein, so oft mit base zu multiplizieren ist also unmöglich. Verwende stattdessen die binäre Exponentiation (Square-and-Multiply): Betrachte die Binärziffern des Exponenten, quadriere die Basis in jedem Schritt und multipliziere sie ins Ergebnis, wenn die Ziffer 1 ist. Für jeden Exponenten hier sind das etwa 60 Schritte.
Implementiere modular_exponentiation(base, exponent, modulus).
Reduziere base zuerst modulo modulus und dann nach jeder Multiplikation erneut. Da modulus ≤ 10^9 ist, liegt das Produkt zweier reduzierter Werte unter 10^18 und passt in eine vorzeichenbehaftete 64-Bit-Ganzzahl.
Eingabe
base: Die Basis.
exponent: Der Exponent, mit dem die Basis potenziert wird.
modulus: Die Zahl, durch die mit Rest geteilt wird.
Ausgabe
Gib base^exponent mod modulus zurück, also einen Wert von 0 bis modulus − 1. Behandle base^0 für jede Basis als 1, auch für 0, sodass die Antwort für den Exponenten 0 gleich 1 mod modulus ist.
Einschränkungen
0 ≤ base ≤ 10^18
0 ≤ exponent ≤ 10^18
1 ≤ modulus ≤ 10^9
Beispiele
Eingabe:
base = 3
exponent = 13
modulus = 50
Erwartete Ausgabe:
expected = 23
Eingabe:
long long base = 3;
long long exponent = 13;
long long modulus = 50;
Erwartete Ausgabe:
long long expected = 23;
Eingabe:
long base = 3;
long exponent = 13;
long modulus = 50;
Erwartete Ausgabe:
long expected = 23;
Erläuterung
3^13 = 1.594.323, und 1.594.323 = 50 × 31.886 + 23, also lautet die Antwort 23.
Eingabe:
base = 2
exponent = 10
modulus = 1000
Erwartete Ausgabe:
expected = 24
Eingabe:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;
Erwartete Ausgabe:
long long expected = 24;
Eingabe:
long base = 2;
long exponent = 10;
long modulus = 1000;
Erwartete Ausgabe:
long expected = 24;
Erläuterung
2^10 = 1024, und 1024 mod 1000 = 24.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Betrachte den Exponenten Binärziffer für Binärziffer, beginnend mit der niedrigsten.
Hinweis 2
Quadriere die Basis in jedem Schritt und multipliziere sie ins Ergebnis, wenn das aktuelle Bit 1 ist.
Hinweis 3
Beginne das Ergebnis mit 1 % modulus, damit Modulus 1 das Ergebnis 0 liefert.
Erwartete Komplexität
Zeit O(log exponent), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.