前两天在 codewars 上做到一道题，题目本身不是很难，但是有一个解法十分厉害，一定要写一篇博客说一下。

原题

For a given list [x1, x2, x3, ..., xn] compute the last (decimal) digit of x1 ^ (x2 ^ (x3 ^ (... ^ xn))).

E. g., last_digit([3, 4, 2]) == 1 because 3 ^ (4 ^ 2) = 3 ^ 16 = 43046721.

Beware: powers grow incredibly fast. For example, 9 ^ (9 ^ 9) has more than 369 millions of digits. lastDigit has to deal with such numbers efficiently.
Corner cases: we assume that 0 ^ 0 = 1 and that lastDigit of an empty list equals to 1.

本人解法

一开始我的思路比较简单：

  • 首先对于一个自然数 n， 有 n ^ x % 10 = (n % 10) ^ x % 10，也就是只要看这个数的个位数的幂结果就行。
  • 其次 1 ~ 9 的幂运算的个位数是不断循环的，且一个循环的长度最多不超过 4 次幂运算。列一张表如下：
底数 幂运算的个位数循环
1 1
2 2 => 4 => 8 => 6
3 3 => 9 => 7 => 1
4 4 => 6
5 5
6 6
7 7 => 9 => 3 => 1
8 8 => 4 => 2 => 6
9 9 => 1
  • 接下来只要从最后一个数开始算，记录每次的幂结果的个位数遍历到第一个数就行了。

但是这个方法没有考虑到 n % 4 != n % 10 % 4，所以还需要改进。

后来和室友讨论了下，每次的幂运算结果不去模 10，模 4 就行了，这样子就能够完美传递幂运算的个位数下去。

模 4 比模 10 的计算方法稍微复杂一些，首先对于任何正整数 n、m 和 x，有 n ^ x % m = (n % m) ^ x % m。下方是一个简单证明。

设 n % m = b，则可以令 n = a * m + b 容易看出 (a * m + b) ^ x % m = b ^ x % m 上面这个式子即 n ^ x % m = (n % m) ^ x % m

然后只要考虑 1 ~ 3 这三个数的幂运算在模 4 时的循环情况就可以。

底数 幂运算的模 4 循环
1 始终为 1
2 1 次幂时为 2，其他为 0
3 奇数次幂为 3，偶数次幂为 1

到这里基本就已经可以做这道题了，我后来再研究的时候发现这个题的结果只与初始数组的前三个元素有关，只需分情况讨论前三个数的奇偶性和是否大于 1 即可，这个展开讲的话太长，我就贴一下我提交的一点都不优雅的代码：

def last_digit(lst):
    loop = ["0", "1", "2486", "3971", "46", "5", "6", "7931", "8426", "91"]
    if len(lst) == 0:
        return 1
    lst[0] %= 10
    temp = lst[::-1]
    while 0 in temp:
        i = temp.index(0)
        if len(temp) >= i + 2:
            temp = [1] + temp[i + 2:]
        elif len(temp) == i + 1:
            return 0
    temp = temp[::-1]
    if len(temp) == 1:
        return temp[0]
    if len(temp) == 2:
        return int(loop[temp[0]][(temp[1] - 1) % len(loop[temp[0]])])
    if temp[0] in [2, 3, 7, 8]:
        if temp[1] % 4 == 3:
            if temp[2] % 2 == 1:
                return int(loop[temp[0]][2])
            else:
                return int(loop[temp[0]][0])
        if temp[1] % 4 == 2:
            if temp[2] <= 1:
                return int(loop[temp[0]][1])
            else:
                return int(loop[temp[0]][3])
        return int(loop[temp[0]][temp[1] % 4 - 1])
    return int(loop[temp[0]][(temp[1] - 1) % len(loop[temp[0]])])

大神的解法

做出了这道题之后就能够看到别人的解法了，我瞟了一下，排名第一的代码直接让我吓得尿了裤子。

def last_digit(lst):
    if not lst:
        return 1
    else:
        out = 1
        for n in lst[len(lst):0:-1]:
            out = n**out
            if out > 2:
                out -= 2
                out %= 4
                out += 2
    return lst[0]**out% 10

感觉这个代码的解法是需要经过严格的数学证明的，但是我到现在还没证出来。如果你看到这个解答后有什么思路请直接在评论中阐述或邮件 liseaside@163.com，万分感谢。