初级编程通关练习题 #8 – 超大数字幂运算

给定两个大数字A和B，求A^B的个位数字。如果是普通数字，A^B幂运算的个位数字就可以很容易计算出来：A ** B % 10。但是如果A和B都是超级大数字，这样的方法就不可行，譬如下面的例子：

数字 a 是 2²⁰⁰，数字 b 是 2³⁰⁰，这时如果直接计算 a^b 是无法在普通电脑上得出结果的。需要采取更快捷的算法来得出两个超级大数字做幂运算后的个位数。

输入样例：

A = 2²⁰⁰，B = 2³⁰⁰

输出样例：

6

算法思路：

• 无论 A 和 B 是多大的数字，幂运算后个位数只和 A 的个位数相关。
• 检查数字1-9的2次幂运算到9次幂运算的结果，我们可以找到个位数出现的规律：

2: 4,8,16,32,64,128,256,512
3: 9,27,81,243,729,2187,6561,19683
4: 16,64,256,1024,4096,16384,65536,262144
5: 25,125,625,3125,15625,78125,390625,1953125
6: 36,216,1296,7776,46656,279936,1679616,10077696
7: 49,343,2401,16807,117649,823543,5764801,40353607
8: 64,512,4096,32768,262144,2097152,16777216,134217728
9: 81,729,6561,59049,531441,4782969,43046721,387420489

• 幂运算个位数重复的规律如下

1 | 1
2 | 4, 8, 6, 2
3 | 9, 7, 1, 3
4 | 6, 4
5 | 5
6 | 6
7 | 9, 3, 1, 7
8 | 4, 2, 6, 8
9 | 1, 9