Algorithmen und Datenstrukturen

Binäre Exponentiation

Gegeben sind drei Zahlen x, n und m. Es soll das Ergebnis von berechnet werden.

Eingabe

Die einzige Zeile der Eingabe enthält 3 ganze Zahlen x, n und m (1 ≤ x, n, m ≤ ).

Ausgabe

Das Programm soll das Ergebnis des Ausdrucks ausgeben.

Beispiele

Eingabe
Ausgabe
2 10 5
4

Erklärung

  1. 2^10 = 1024 ⇒ 1024 mod 5 = 4
 

Tutorial

Da alle Zahlen ziemlich groß sein können, müssen wir einen schnellen Algorithmus verwenden, damit die Berechnung effizient bleibt. 1. Die binäre Exponentiation ist eine effiziente Methode, große Potenzen einer Zahl zu berechnen. Sie verringert die Anzahl der Multiplikationen, was sie schneller macht als die traditionelle Methode, bei der man von 1 bis n iteriert und jedes Mal das Ergebnis mit x multipliziert.
 
Der Algorithmus der binären Exponentiation basiert auf der folgenden mathematischen Beobachtung: Wenn wir eine Zahl x haben, die in der Potenz n steht, dann kann folgendermaßen dargestellt werden:
  • , wenn n gerade ist
  • , wenn n ungerade ist
Das beschleunigt den Berechnungsprozess erheblich, da wir nur einmal berechnen und das Ergebnis anschließend miteinander multiplizieren. Der Algorithmus kann zum Beispiel so aussehen:
def binpow(x, n, m):
    if n == 0:                        # Basisfall: x^0 = 1
        return 1
    if n % 2 == 0:                    # n ist gerade => Hälfte berechnen und multiplizieren
        half = binpow(x, n // 2, m)   # Hälfte berechnen
        return (half * half) % m      # Ergebnis = x^(n/2) * x^(n/2)

    # n ist ungerade => Ergebnis = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
Dank der binären Exponentiation wird die Zeitkomplexität von auf reduziert, da wir in jedem Schritt bei geradem n den Exponenten halbieren. Wichtig ist dabei, dass bei ungeradem n der Exponent für den nächsten Schritt automatisch gerade wird.
Lassen Sie uns den Algorithmus an einem Beispiel durchgehen:
x = 2, n = 10 (wir ignorieren m der Einfachheit halber)
  1. [n = 10] → n % 2 == 0 ⇒ binpow(2, 5) berechnen
  1. [n = 5] → n % 2 ≠ 0 ⇒ gibt 2 * binpow(2, 4) zurück
  1. [n = 4] → n % 2 == 0 ⇒ binpow(2, 2) berechnen
  1. [n = 2] → n % 2 == 0 ⇒ binpow(2, 1) berechnen
  1. [n = 1] ⇒ n % 2 ≠ 0 ⇒ gibt 2 * binpow(2, 0) zurück
  1. [n = 0] ⇒ n == 0 ⇒ gibt 1 zurück
  1. [bis n = 1] ⇒ gibt 2 * 1 = 2 zurück
  1. [bis n = 2] ⇒ gibt 2 * 2 = 4 zurück
  1. [bis n = 4] ⇒ gibt 4 * 4 = 16 zurück
  1. [bis n = 5] ⇒ gibt 2 * 16 = 32 zurück
  1. [bis n = 10] ⇒ gibt 32 * 32 = 1024 zurück
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue