letzte Ziffer einer^b^c

Question

Ich habe auf dieses Problem stecken haben:

a, b und c drei natürlichen Zahlen gegeben (so dass 1 < = a, b, c < = 10^9), haben Sie die letzte Ziffer der Zahl a^b^c finden soll.“

Was ich zuerst gedacht habe, war eine an Macht n der O (log n) Algorithmus für das Anheben.

int acc=1; //accumulator 
    while(n>0) { 
     if(n%2==1) 
      acc*=a; 
     a=a*a; 
     n/=2; 
    } 

Offensichtlich könnten einige grundlegende mathematische helfen, wie die „letzte Ziffer“ stuff:

Last_digit(2^n) = Last_digit(2^(n%4)) 

Wo n% 4 ist der Rest der Division n/4

Auf den Punkt gebracht, ich habe versucht, zu kombinieren diese, aber ich kam nicht auf den guten Weg.

würde Einige helfen wirklich apreciated.

Answer 1

Das Problem ist, dass b^c sehr groß sein kann. Sie möchten es also reduzieren, bevor Sie die modulare Standardexponentiation verwenden.

können Sie bemerken, dass a^(b^c) MOD 10 maximal 10 verschiedene Werte haben können.

Wegen des Schubfachprinzip wird es eine Reihe p so beschaffen sein, dass für einige r:

a^r MOD 10 = a^(p+r) MOD 10 
p <= 10 
r <= 10 

Dies bedeutet, dass für jede q:

a^r MOD 10 = a^r*a^p MOD 10 
      = (a^r*a^p)*a^p MOD 10 
      = ... 
      = a^(r+q*p) MOD 10 

Für n = s+r+q*p, mit s < p Sie haben:

a^n MOD 10 = a^s*a^(r+q*p) MOD 10 
      = a^s*a^r MOD 10 
      = a^((n-r) MOD p)*a^r MOD 10 

Sie können einfach n= (b^c) in der vorherigen Gleichung ersetzen.

Sie berechnen nur (b^c-r) MOD p, wobei p <= 10 was einfach ist, und berechnen Sie dann a^((b^c-r) MOD p)*a^r MOD 10.

Answer 2

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)