Ich habe bei diesem Problem feststecken:
Gegeben a, b und c drei natürliche Zahlen (so dass 1 & lt; = a, b, c & lt; = 10 ^ 9), sollst du die letzte Ziffer der Zahl a ^ b ^ c finden. "
Was ich zuerst dachte, war der O (log n) -Algorithmus, um eine at-Potenz n zu erhöhen.
%Vor%Offensichtlich kann einige grundlegende Mathematik helfen, wie die "letzte Ziffer" Zeug:
%Vor%Dabei ist n% 4 der Rest der Division n / 4
Kurz gesagt, ich habe versucht, diese zu kombinieren, aber ich kam nicht auf den guten Weg.
Einige Hilfe würde wirklich geschätzt werden.
Das Problem ist, dass b^c sehr groß sein kann. Sie möchten es also reduzieren, bevor Sie die standardmäßige modulare Potenzierung verwenden.
Sie können bemerken, dass a^(b^c) MOD 10 maximal 10 verschiedene Werte haben kann.
Wegen des Schubladendenkenprinzips gibt es eine Zahl p , so dass für einige r :
Dies bedeutet, dass für jedes q :
Für n = s+r+q*p , mit s < p gilt:
Sie können n= (b^c) in der vorherigen Gleichung ersetzen.
Sie berechnen nur (b^c-r) MOD p wo p <= 10 , was einfach ist und berechnen dann a^((b^c-r) MOD p)*a^r MOD 10 .
Wie ich bereits in meinen Kommentaren erwähnt habe, hat das wirklich nicht viel mit intelligenten Algorithmen zu tun. Das Problem kann vollständig unter Verwendung einer elementaren Zahlentheorie reduziert werden. Dies ergibt einen O (1) -Algorithmus.
Der chinesische Restsatz besagt, dass, wenn wir eine Zahl x modulo 2 und modulo 5 kennen, wir sie modulo 10 kennen. Also kann man a ^ b ^ c modulo 10 finden, indem man a ^ b ^ c modulo 2 und a findet ^ b ^ c modulo 5. Fermats kleiner Satz sagt, dass für jede Primzahl p, wenn p nicht a teilt, dann a ^ (p-1) = 1 (mod p), also a ^ n = a ^ (n mod ( p-1)) (Mod p). Wenn p a teilt, dann ist offensichtlich a ^ n = 0 (mod p) für jedes n & gt; 0. Beachten Sie, dass x ^ n = x (mod 2) für jedes n & gt; 0 gilt, also a ^ b ^ c = a (mod 2).
Was bleibt, ist a ^ b ^ c mod 5 zu finden, was sich auf das Finden von b ^ c mod 4 reduziert. Leider können wir weder den chinesischen Restsatz noch Fermat's kleinen Satz hier verwenden. Allerdings gibt es für Mod 4 nur 4 Möglichkeiten, also können wir sie separat prüfen. Wenn wir mit b = 0 (mod 4) oder b = 1 (mod 4) beginnen, dann ist natürlich b ^ c = b (mod 4). Wenn wir b = 2 (mod 4) haben, dann ist leicht ersichtlich, dass b ^ c = 2 (mod 4), wenn c = 1, und b ^ c = 0 (mod 4), wenn c & gt; 1. Wenn b = 3 (mod 4), dann ist b ^ c = 3, wenn c gerade ist, und b ^ c = 1, wenn c ungerade ist. Dies gibt uns b ^ c (mod 4) für jedes b und c, das uns dann a ^ b ^ c (mod 5) gibt, alles in konstanter Zeit.
Schließlich können wir mit a ^ b ^ c = a (mod 2) den chinesischen Restsatz verwenden, um a ^ b ^ c (mod 10) zu finden. Dies erfordert eine Abbildung zwischen (x (mod 2), y (mod 5)) und z (mod 10). Der chinesische Restsatz sagt uns nur, dass diese Abbildung bijektiv ist, sie sagt uns nicht, wie wir sie finden. Es gibt jedoch nur 10 Optionen, so dass dies leicht auf einem Blatt Papier oder mit einem kleinen Programm erledigt werden kann. Sobald wir dieses Mapping gefunden haben, speichern wir es einfach in einem Array und können die gesamte Berechnung in O (1) durchführen.
Das wäre übrigens die Implementierung meines Algorithmus in Python:
%Vor%Tags und Links math exponentiation