Wie ich in meinen Kommentaren erwähnt, das ist 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. Das chinesische Resttheorem besagt, dass, wenn wir eine Zahl x modulo 2 und modulo 5 kennen, wir es modulo 10 kennen. Also kann man a^b^c modulo 10 finden, um a^b^c modulo 2 und zu finden a^b^c modulo 5. Fermats kleiner Satz besagt, dass für jede Primzahl p, wenn p a nicht 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> 0. Beachten Sie, dass x^n = x (mod 2) für jedes n> 0, also a^b^c = a (mod 2).
Was übrig bleibt ist, einen^b^c mod 5 zu finden, der 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> 1. Wenn b = 3 (mod 4) dann 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.
By the way, wäre dies die Umsetzung meines Algorithmus in Python sein:
# this table only needs to be calculated once
# can also be hard-coded
mod2mod5_to_mod10 = [[0 for i in range(5)] for j in range(2)]
for i in range(10):
mod2mod5_to_mod10[i % 2][i % 5] = i
[a,b,c] = [int(input()) for i in range(3)]
if a % 5 == 0:
abcmod5 = 0
else:
if b % 4 == 0 or b % 4 == 1:
bcmod4 = b % 4
elif b == 2:
if c == 1:
bcmod4 = 2
else:
bcmod4 = 0
else:
if c % 2 == 0:
bcmod4 = 1
else:
bcmod4 = 3
abcmod5 = ((a % 5)**bcmod4) % 5
abcmod2 = a % 2
abcmod10 = mod2mod5_to_mod10[abcmod2][abcmod5]
print(abcmod10)
Beachten Sie, dass Sie sollten diese zu reduzieren, vollständig in der Lage sein, wenn Sie Fermats kleinen Satz und den chinesischen Restsatz verwenden. Mit anderen Worten, mit etwas Mathematik sollten Sie in der Lage sein, einen O (1) -Algorithmus zu entwickeln. – JSQuareD
Wenn Sie eine Zahl "a" zu größeren und größeren Kräften erhöhen, beginnt die letzte Ziffer zu durchlaufen. Können Sie herausfinden, wie Sie bestimmen können, wo im Zyklus Sie landen, ohne alle "b^c" zu berechnen? – user2357112
@ Scummy der Punkt (denke ich) ist, dass 10 = 2 * 5 und 2,5 Primzahlen sind. CRT kann Ihnen erlauben, das Ergebnis mod 10 mit den Ergebnissen mod 2 und mod 5 zu finden. –