我需要找到x1 ^ (x2 ^ (x3 ^ (... ^ xn)))作為列表傳遞給函數(shù)的整數(shù)的單位數(shù)字。例如，輸入[3, 4, 2]將返回，1因為它3 ^ (4 ^ 2) = 3 ^ 16 = 43046721的最后一位是 1。該函數(shù)需要盡可能高效，因為顯然嘗試計算767456 ^ 981242不是很快。我嘗試了幾種方法，但我認為解決這個問題的最好方法是使用序列。例如，任何以 a 結(jié)尾的數(shù)字1，當(dāng)求冪時，總是以 結(jié)尾1。對于2，結(jié)果數(shù)字將以 或 結(jié)尾2, 4, 6 or 8。如果將一個數(shù)字進行冪運算，則結(jié)果數(shù)字的最后一位數(shù)字將遵循基于指數(shù)最后一位數(shù)字的模式：1：序列為 12：序列為 2, 4, 8, 63：序列為 3, 9, 7, 14：順序是4、65：序列為 56：序列為 67：序列為 7, 9, 3, 18：序列為 8、4、2、69：序列為 9、10：序列為 0我認為計算整體最后一位數(shù)字的最簡單方法是向后計算列表并一次計算每個計算的最后一位數(shù)字，直到我回到開始，但我不知道如何做到這一點？如果有人可以幫助或建議另一種與此相同或更有效的方法，我們將不勝感激。到目前為止我有這個代碼，但它不適用于非常大的數(shù)字
3 回答
白衣染霜花
TA貢獻1796條經(jīng)驗 獲得超10個贊
def last_digit(lst):
if lst == []:
return 1
total = lst[len(lst)-2] ** lst[len(lst)-1]
for n in reversed(range(len(lst)-2)):
total = pow(lst[n], total)
return total%10
編輯：0 ^ 0應(yīng)該假設(shè)為1
明月笑刀無情
TA貢獻1828條經(jīng)驗 獲得超4個贊
x^n = x^(n%4) 因為最后一位數(shù)字的周期總是 4。
x ^2 ^3 ^4 ^5
1 1 1 1 1
2 4 8 6 2
3 9 7 1 3
4 6 4 6 4
5 5 5 5 5
6 6 6 6 6
7 9 3 1 7
8 4 2 6 8
9 1 9 1 9
如您所見，所有 9 位數(shù)字的句點都是 4，因此我們可以使用 %4 來簡化計算。
如果我們這樣做 %4，也有一個模式。
x ^0 ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9
1 1 1 1 1 1 1 1 1 1 1
2 1 2 0 0 0 0 0 0 0 0
3 1 3 1 3 1 3 1 3 1 3
4 1 0 0 0 0 0 0 0 0 0
5 1 1 1 1 1 1 1 1 1 1 (all %4)
6 1 2 0 0 0 0 0 0 0 0
7 1 3 1 3 1 3 1 3 1 3
8 1 0 0 0 0 0 0 0 0 0
9 1 1 1 1 1 1 1 1 1 1
如圖所示，當(dāng) n>1 時，每個 x 都有一個模式。因此，當(dāng) n>1 時，您可以看到 (x^n)%4 = (x^(n+4k))%4。然后我們可以通過將 4 添加到 n 來防止由 n=0 和 n=1 引起的問題。這是因為，如果 (x^n)%4 = (x^(n+4k))%4，那么 (x^n)%4 = (x^(n%4+4))%4 也是如此。
powers = [3, 9, 7, 1]
lastDigit = 1
for i in range(len(powers) - 1, -1, -1):
if lastDigit == 0:
lastDigit = 1
elif lastDigit == 1:
lastDigit = powers[i]
else:
lastDigit = powers[i]**(lastDigit%4+4)
print(lastDigit%10)
30秒到達戰(zhàn)場
TA貢獻1828條經(jīng)驗 獲得超6個贊
這更像是數(shù)學(xué)而不是編程。請注意，您列出的所有序列的長度都是 1、2 或 4。更準(zhǔn)確地說，x^4始終以 或 結(jié)尾0, 1, 5, 6， 也是x^(4k)。所以如果你知道x^(m mod 4) mod 10，你就知道x^m mod 10。
現(xiàn)在，計算x2^(x3^(...^xn)) mod 4. 故事非常相似，x^2 mod 4是以太0如果x=2k或1如果x=2k+1（為什么？）。所以
如果 x2 == 0，則為 0
如果 x2 > 0 且 x3 == 0，則為 1
如果
x2是偶數(shù)，則它是2or 或0with2僅在 時發(fā)生x2 mod 4 == 2 and (x3==1 or (any x4,...xn == 0) )。if
x2是奇數(shù)，那么x2^2 mod 4 == 1，所以我們得到1ifx3是偶數(shù) elsex2 mod 4。
足夠的數(shù)學(xué)，讓我們談?wù)劸幋a?？赡苡形覜]有涵蓋的極端情況，但它應(yīng)該適用于大多數(shù)情況。
def last_digit(lst):
if len(lst) == 0:
return 1
x = lst[0] % 10
if len(lst) == 1:
return x
# these number never change
if x in [0,1,5,6]:
return x
# now we care for x[1] ^ 4:
x1 = x[1] % 4
# only x[0] and x[1]
if len(lst) == 2 or x1==0:
return x[0] ** x1 % 10
# now that x[2] comes to the picture
if x1 % 2: # == 1
x1_pow_x2 = x1 if (x[2]%2) else 1
else:
x1_pow_x2 = 2 if (x1==2 and x[2]%2 == 1) else 0
# we almost done:
ret = x ** x1_pow_x2 % 10
# now, there's a catch here, if x[1]^(x[2]^...^x[n-1]) >= 4,
# we need to multiply ret with the last digit of x ** 4
if x[1] >=4 or (x[1] > 1 and x[2] > 1):
ret = (ret * x**4) % 10
return ret
添加回答
舉報
0/150
提交
取消