Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Modulare Exponentiation

Berechne eine Potenz modulo einer Zahl mit schneller Exponentiation.

Das lernst du

  • Eine Zahl in O(log exponent) Schritten mit einem riesigen Exponenten potenzieren
  • Jeden Zwischenwert reduziert halten, um Überlauf zu vermeiden
  • Exponent 0 und Modulus 1 behandeln

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.