Przeanalizuj sobie powtarzające się wzory, w zależności jaka jest ostatnia cyfra liczby podnoszonej do potęgi; szczęśliwie one się powtarzają z okresem maksymalnie 4. Czyli, łatwo znaleźć zależność modulo dająca ostatnią cyfrę, w zalezności od ostataniej cyfry liczby potęgowanej. Złożoność będzie stała, plus złożoność modulo, pseudokod:
fun las_digit(n, k):
if n % 10 == 0:
return 0
if n % 10 == 1:
return 1
if n % 10 == 5:
return 5
if n % 10 == 6:
return 6
if n % 10 == 2:
digits = [2, 4, 8, 6]
tmp_rest = k % 4
if tmp_rest == 0: ## Jak dzieli się bez reszty to wzór powtórzy się jakieś m razy 4 czyli ostatnia cyfra:
return digits[-1] ## by convention array[-1] returns the last intem in the array
else:
return digits[tmp_rest - 1] ## jak nie to zwracam kolejne z tablicy (reszta) ( -1, bo indeksowanie od 0)
if n % 10 == 3:
digits = [3, 9, 7, 1]
tmp_rest = k % 4
if tmp_rest == 0:
return digits[-1]
else:
return digits[tmp_rest - 1]
if n % 10 == 4:
digits = [4, 6]
tmp_rest = k % 2
if tmp_rest == 0:
return digits[-1]
else:
return digits[tmp_rest - 1]
if n % 10 == 7:
digits = [7, 9, 3, 1]
tmp_rest = k % 4
if tmp_rest == 0:
return digits[-1]
else:
return digits[tmp_rest - 1]
if n % 10 == 8:
digits = [8, 4, 2, 6]
tmp_rest = k % 4
if tmp_rest == 0:
return digits[-1]
else:
return digits[tmp_rest - 1]
if n % 10 == 9:
digits = [9, 1]
tmp_rest = k % 2
if tmp_rest == 0:
return digits[-1]
else:
return digits[tmp_rest - 1]