如何以最简单的方式找到某个功率的单位数字

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种可能性,然后它会在同一个循环中重复.

在欧拉定理的帮助下,我们可以证明这适用于任何整数n,这意味着它们的单位数将在最多4个连续指数之后重复.仅查看任意乘积的单位数相当于乘以模10的乘法的余数,例如:

2^7 % 10 = 128 % 10 = 8 

它也可以显示(并且非常直观)对于任意基数,任何功率的单位数将仅取决于基数本身的单位数 - 即2013 ^ 2013具有与3 ^ 2013相同的单位数.

我们可以利用这两个事实来提出一个非常快速的算法(感谢您的帮助 - 我可以提供更快的版本).

这个想法是这样的:正如我们所知,对于任何数字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到

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

现在为了尽可能提高效率,我们将对基本的算术运算进行一些调整:

• 乘以4相当于向左移动两个('<< 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

也就是说,^ 5产生与^ 1相同的单位数字,依此类推.

从欧拉定理我们知道

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

其中phi(10)是1到10之间的数字,它们是10的共同素数(即它们的gcd等于1).数字<10 co-prime到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)^ yi将被10整除.

Answer 2

我确信有一个合适的数学方法可以解决这个问题,但我建议你,因为你只关心最后一个数字,因为理论上每个数字本身重复乘以最终会产生一个重复模式(当只查看最后一个数字时) ),您可以简单地执行乘法,直到您检测到第一次重复,然后将指数映射到您构建的模式中的适当位置.

请注意,因为您只关心最后一位数字,所以在开始构建模式映射之前,可以通过将输入数字截断为其一位数来进一步简化操作.这将允许您确定最后一个数字,即使是任意大的输入,否则会导致第一次或第二次乘法溢出.

这是JavaScript中的一个基本示例:http: //jsfiddle.net/dtyuA/2/

3^2011顺便说一句,最后一位是7.

Answer 3

你应该看一下Modular取幂.你想要的是用m = 10 来计算n ^ e(mod m).这与计算除以10的n ^ e的余数相同.

您可能对从右到左的二进制方法计算它感兴趣,因为它是最节省时间的方法最简单的不太难实现.这是来自维基百科的伪代码:

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent & 1) equals 1:
           result = (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

在那之后,只需用模数= 10来调用你想要的基数和指数,这就是你的答案.

编辑:对于一个更简单的方法,CPU效率更低但内存更多,请查看维基百科上文章的内存效率部分.逻辑很简单:

function modular_pow(base, exponent, modulus)
    c := 1
    for e_prime = 1 to exponent 
        c := (c * base) mod modulus
    return c