ultima cifra di un^b^c

Question

ho rimasto bloccato su questo problema:

Dato a, b e c tre numeri naturali (tale che 1 < = a, b, c < = 10^9), si suppone per trovare l'ultima cifra del numero a^b^c."

Quello che ho pensato in primo luogo era la O (log n) algoritmo per crescere un all'accensione n.

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

Ovviamente, alcuni matematica di base potrebbe aiutare, come la "ultima cifra" roba:

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

Dove n% 4 è il resto della divisione n/4

In poche parole, ho cercato di coniugare questi, ma non ho potuto ottenere sulla buona strada.

Alcuni aiuti sarebbero davvero apprezzati.

Answer 1

Il problema è che b^c potrebbe essere molto grande. Quindi vuoi ridurlo prima di usare l'esponenziazione modulare standard.

È possibile notare che a^(b^c) MOD 10 può avere un massimo di 10 valori diversi.

A causa del principio dei cassetti, ci sarà un certo numero p tale che per alcuni r:

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

Questo implica che per ogni 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 

Per qualsiasi n = s+r+q*p, con s < p voi avere:

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 

È possibile sostituire solo n= (b^c) nell'equazione precedente.

Si calcola solo (b^c-r) MOD p dove p <= 10 che è facilmente possibile e quindi calcolare a^((b^c-r) MOD p)*a^r MOD 10.

Answer 2

Come ho detto nei miei commenti, questo non ha molto a che fare con gli algoritmi intelligenti. Il problema può essere ridotto completamente usando una teoria dei numeri elementari. Questo produrrà un algoritmo O (1).

Il teorema del resto cinese dice che se conosciamo qualche numero x modulo 2 e modulo 5, lo conosciamo modulo 10. Quindi trovare un^b^c modulo 10 può essere ridotto alla ricerca di un^b^c modulo 2 e a^b^c modulo 5. Il piccolo teorema di Fermat dice che per ogni primo p, se p non divide a, allora a^(p-1) = 1 (mod p), quindi a^n = a^(n mod (p-1)) (mod p). Se p divide a, allora ovviamente a^n = 0 (mod p) per ogni n> 0. Si noti che x^n = x (mod 2) per ogni n> 0, quindi a^b^c = a (mod 2).

Ciò che rimane è trovare un^b^c mod 5, che si riduce a trovare b^c mod 4. Sfortunatamente, non possiamo usare né il teorema del remainder cinese, né il piccolo teorema di Fermat qui. Tuttavia, mod 4 ci sono solo 4 possibilità per b, quindi possiamo verificarle separatamente. Se iniziamo con b = 0 (mod 4) o b = 1 (mod 4), quindi ovviamente b^c = b (mod 4).Se abbiamo b = 2 (mod 4) allora è facilmente visto che b^c = 2 (mod 4) se c = 1, e b^c = 0 (mod 4) se c> 1. If b = 3 (mod 4) quindi b^c = 3 se c è pari, e b^c = 1 se c è dispari. Questo ci dà b^c (mod 4) per ogni b e c, che poi ci dà un^b^c (mod 5), tutto in tempo costante.

Infine con a^b^c = a (mod 2) possiamo usare il teorema del resto cinese per trovare a^b^c (mod 10). Ciò richiede una mappatura tra (x (mod 2), y (mod 5)) e z (mod 10). Il teorema del resto cinese ci dice solo che questa mappatura è biiettiva, non ci dice come trovarla. Tuttavia, ci sono solo 10 opzioni, quindi questo è facilmente fatto su un pezzo di carta o usando un piccolo programma. Una volta trovata questa mappatura, la archiviamo semplicemente in un array e possiamo eseguire l'intero calcolo in O (1).

Tra l'altro, questo sarebbe l'attuazione del mio algoritmo in Python:

# 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)