algorithm - 怎样用最简单的方法求某次幂的个位数

Question

如何找出某个数字的个位数(例如 3 power 2011)。我应该使用什么逻辑来找到这个问题的答案？

Answer 1

对于基数 3:

3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
...

也就是说个位数字只有 4 种可能性，然后它会在同一个循环中重复出现。

在Euler's theorem的帮助下我们可以证明这适用于任何整数 n，这意味着它们的单位数字将在最多 4 个连续的指数之后重复。只看任意乘积的个位数相当于乘法取余数模10，例如:

2^7 % 10 = 128 % 10 = 8 

还可以证明(并且非常直观)对于任意底数，任何幂的个位数将仅取决于底数本身的个位数 - 即 2013^2013 与 3 具有相同的个位数^2013。

我们可以利用这两个事实来提出一个极快的算法(感谢 help - 如果允许我可以提供一个更快的版本)。

想法是这样的:正如我们所知，对于任何数字 0-9 最多会有 4 种不同的结果，我们也可以将它们存储在查找表中:

{ 0,0,0,0, 1,1,1,1, 6,2,4,8, 1,3,9,7, 6,4,6,4, 
  5,5,5,5, 6,6,6,6, 1,7,9,3, 6,8,4,2, 1,9,1,9 }

这是 0-9 的可能结果，按顺序分成四组。现在的想法是求幂 n^a 到

• 首先取基模 10 => := i
• 转到我们表中的索引 4*i(它是该特定数字的起始偏移量)
• 取指数 mod 4 => := off(正如欧拉定理所述，我们只有四种可能的结果!)
• 在4*i中加入off得到结果

现在为了使其尽可能高效，对基本算术运算应用了一些调整:

• 乘以4相当于左移2('<< 2')
• 取一个数 a % 4 等同于说 a&3(屏蔽 1 和 2 位，形成余数 % 4)

---

C中的算法:

static int table[] = {
    0, 0, 0, 0, 1, 1, 1, 1, 6, 2, 4, 8, 1, 3, 9, 7, 6, 4, 6, 4, 
    5, 5, 5, 5, 6, 6, 6, 6, 1, 7, 9, 3, 6, 8, 4, 2, 1, 9, 1, 9
};

int /* assume n>=0, a>0 */ 
unit_digit(int n, int a)
{
    return table[((n%10)<<2)+(a&3)];
}

---

初始声明的证明

通过观察，我们注意到 3^x 的个位数每四次方重复一次。声称这适用于任何整数。但这实际上是如何证明的呢？事实证明，使用模块化算法非常容易。如果我们只对个位数感兴趣，我们可以执行模 10 的计算。这相当于说 4 个指数后的个位数循环或说

a^4 congruent 1 mod 10

如果这个成立，那么举例

a^5 mod 10 = a^4 * a^1 mod 10 = a^4 mod 10 * a^1 mod 10 = a^1 mod 10

也就是说，a^5 产生与 a^1 等相同的个位数。

来自 Euler's theorem我们知道

a^phi(10) mod 10 = 1 mod 10

其中 phi(10) 是 1 到 10 之间与 10 互质的数(即它们的 gcd 等于 1)。 < 10 与 10 互质的数字是 1、3、7 和 9。所以 phi(10) = 4 这证明确实 a^4 mod 10 = 1 mod 10。

要证明的最后一个声明是，对于基数 >= 10 的幂运算，只需查看基数的个位数就足够了。假设我们的基数是 x >= 10，那么我们可以说 x = x_0 + 10*x_1 + 100*x_2 + ...(基数 10 表示)

使用模块化表示很容易看出这一点

x ^ y mod 10
= (x_0 + 10*x_1 + 100*x_2 + ...) ^ y mod 10
= x_0^y + a_1 * (10*x_1)^y-1 + a_2 * (100*x_2)^y-2 + ... + a_n * (10^n) mod 10
= x_0^y mod 10  

其中 a_i 是包含 x_0 次幂但最终不相关的系数，因为整个乘积 a_i * (10 * x_i)^y-i 将被 10 整除。