当前位置：文江博客话题详情

如何用最简单的方法求某次幂的个位数

发布于 2024-12-01 23:26:02 字数 68 浏览 2 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

穿透光 2024-12-08 23:26:02

对于基数 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

首先取基模 10 => := i
转到表中的索引 4*i （它是该特定数字的起始偏移量），
取指数 mod 4 =>; := off （根据欧拉定理，我们只有四种可能的结果！）
将 off 添加到 4*i 即可得到结果

Now to为了尽可能高效，对基本算术运算进行了一些调整：

乘以 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 等等。

从欧拉定理我们知道，

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)^yi 将被 10 整除。

For base 3:

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

That is the units digit has only 4 possibilities and then it repeats in ever the same cycle.

With the help of Euler's theorem we can show that this holds for any integer n, meaning their units digit will repeat after at most 4 consecutive exponents. Looking only at the units digit of an arbitrary product is equivalent to taking the remainder of the multiplication modulo 10, for example:

2^7 % 10 = 128 % 10 = 8

It can also be shown (and is quite intuitive) that for an arbitrary base, the units digit of any power will only depend on the units digit of the base itself - that is 2013^2013 has the same units digit as 3^2013.

We can exploit both facts to come up with an extremely fast algorithm (thanks for the help - with kind permission I may present a much faster version).

The idea is this: As we know that for any number 0-9 there will be at most 4 different outcomes, we can as well store them in a lookup 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 }

That's the possible outcomes for 0-9 in that order, grouped in fours. The idea is now for an exponentiation n^a to

first take the base mod 10 => := i
go to index 4*i in our table (it's the starting offset of that particular digit)
take the exponent mod 4 => := off (as stated by Euler's theorem we only have four possible outcomes!)
add off to 4*i to get the result

Now to make this as efficient as possible, some tweaks are applied to the basic arithmetic operations:

Multiplying by 4 is equivalent to shifting two to the left ('<< 2')
Taking a number a % 4 is equivalent to saying a&3 (masking the 1 and 2 bit, which form the remainder % 4)

The algorithm in 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)];
}

Proof for the initial claims

From observing we noticed that the units digit for 3^x repeats every fourth power. The claim was that this holds for any integer. But how is this actually proven? As it turns out that it's quite easy using modular arithmetic. If we are only interested in the units digit, we can perform our calculations modulo 10. It's equivalent to say the units digit cycles after 4 exponents or to say

a^4 congruent 1 mod 10

If this holds, then for example

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

that is, a^5 yields the same units digit as a^1 and so on.

From Euler's theorem we know that

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

where phi(10) is the numbers between 1 and 10 that are co-prime to 10 (i.e. their gcd is equal to 1). The numbers < 10 co-prime to 10 are 1,3,7 and 9. So phi(10) = 4 and this proves that really a^4 mod 10 = 1 mod 10.

The last claim to prove is that for exponentiations where the base is >= 10 it suffices to just look at the base's units digit. Lets say our base is x >= 10, so we can say that x = x_0 + 10*x_1 + 100*x_2 + ... (base 10 representation)

Using modular representation it's easy to see that indeed

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

where a_i are coefficients that include powers of x_0 but finally not relevant since the whole product a_i * (10 * x_i)^y-i will be divisible by 10.

回复收藏 0 原文

稳稳的幸福 2024-12-08 23:26:02

您应该查看模幂。您想要的与计算 m = 10 的 n^e (mod m) 相同。这与计算 n^e 除以 10 的余数相同。

您可能对从右到左二进制方法计算感兴趣它，因为它是最省时的，并且~~最简单~~实现起来并不难。这是来自维基百科的伪代码：

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

之后，只需用 modulus = 10 调用它即可获得您想要的底数和指数，这就是您的答案。

编辑：对于更简单的方法，CPU 效率较低但内存效率更高，请查看内存效率部分。逻辑很简单：

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

You should look at Modular exponentiation. What you want is the same of calculating n^e (mod m) with m = 10. That is the same thing as calculating the remainder of the division by ten of n^e.

You are probably interested in the Right-to-left binary method to calculate it, since it's the most time-efficient one and ~~the easiest~~ not too hard to implement. Here is the pseudocode, from Wikipedia:

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

After that, just call it with modulus = 10 for you desired base and exponent and there's your answer.

EDIT: for an even simpler method, less efficient CPU-wise but more memory-wise, check out the Memory-efficient section of the article on Wikipedia. The logic is straightforward enough:

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

回复收藏 0 原文

情独悲 2024-12-08 23:26:02

我确信有一种正确的数学方法可以解决这个问题，但我建议，因为您只关心最后一位数字，并且理论上每个数字与其自身重复相乘最终应该生成重复模式（当仅查看最后一位数字时）），您可以简单地执行乘法，直到检测到第一个重复，然后将指数映射到您构建的模式中的适当位置。

请注意，因为您只关心最后一位数字，所以您可以在开始构建模式映射之前将输入数字截断为个位数，从而进一步简化事情。这将使您即使对于任意大的输入也能确定最后一位数字，否则会导致第一次或第二次乘法溢出。

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

function lastDigit(base, exponent) {
  if (exponent < 0) {
    alert("stupid user, negative values are not supported");
    return 0;
  }
  if (exponent == 0) {
    return 1;
  }
  var baseString = base + '';
  var lastBaseDigit = baseString.substring(baseString.length - 1);
  var lastDigit = lastBaseDigit;
  var pattern = [];

  do {
    pattern.push(lastDigit);
    var nextProduct = (lastDigit * lastBaseDigit) + '';
    lastDigit = nextProduct.substring(nextProduct.length - 1);
  } while (lastDigit != lastBaseDigit);

  return pattern[(exponent - 1) % pattern.length];
};

function doMath() {
  var base = parseInt(document.getElementById("base").value, 10);
  var exp = parseInt(document.getElementById("exp").value, 10);
  console.log(lastDigit(base, exp));
};

console.log(lastDigit(3003, 5));

Base: <input id="base" type="text" value="3" /> <br> 
Exponent: <input id="exp" type="text" value="2011"><br>
<input type="button" value="Submit" onclick="doMath();" />

顺便说一句，3^2011 中的最后一位数字是 7。

I'm sure there's a proper mathematical way to solve this, but I would suggest that since you only care about the last digit and since in theory every number multiplied by itself repeatedly should generate a repeating pattern eventually (when looking only at the last digit), you could simply perform the multiplications until you detect the first repetition and then map your exponent into the appropriate position in the pattern that you built.

Note that because you only care about the last digit, you can further simplify things by truncating your input number down to its ones-digit before you start building your pattern mapping. This will let you to determine the last digit even for arbitrarily large inputs that would otherwise cause an overflow on the first or second multiplication.

Here's a basic example in JavaScript: http://jsfiddle.net/dtyuA/2/

function lastDigit(base, exponent) {
  if (exponent < 0) {
    alert("stupid user, negative values are not supported");
    return 0;
  }
  if (exponent == 0) {
    return 1;
  }
  var baseString = base + '';
  var lastBaseDigit = baseString.substring(baseString.length - 1);
  var lastDigit = lastBaseDigit;
  var pattern = [];

  do {
    pattern.push(lastDigit);
    var nextProduct = (lastDigit * lastBaseDigit) + '';
    lastDigit = nextProduct.substring(nextProduct.length - 1);
  } while (lastDigit != lastBaseDigit);

  return pattern[(exponent - 1) % pattern.length];
};

function doMath() {
  var base = parseInt(document.getElementById("base").value, 10);
  var exp = parseInt(document.getElementById("exp").value, 10);
  console.log(lastDigit(base, exp));
};

console.log(lastDigit(3003, 5));

Base: <input id="base" type="text" value="3" /> <br> 
Exponent: <input id="exp" type="text" value="2011"><br>
<input type="button" value="Submit" onclick="doMath();" />

And the last digit in 3^2011 is 7, by the way.

回复收藏 0 原文

岁月蹉跎了容颜 2024-12-08 23:26:02

我们可以首先检查以 10 为基数的数字连续幂得到的每个结果的最后一位数字：

d      d^2    d^3    d^4    d^5    d^6    d^7    d^8    d^9 (mod 10)
---    ---    ---    ---    ---    ---    ---    ---    ---
0      0      0      0      0      0      0      0      0
1      1      1      1      1      1      1      1      1
2      4      8      6      2      4      8      6      2
3      9      7      1      3      9      7      1      3
4      6      4      6      4      6      4      6      4
5      5      5      5      5      5      5      5      5
6      6      6      6      6      6      6      6      6
7      9      3      1      7      9      3      1      7
8      4      2      6      8      4      2      6      8
9      1      9      1      9      1      9      1      9

我们可以看到，在所有情况下，最后一位数字循环不超过四个不同的值。利用这个事实，并假设 n 是一个非负整数，p 是一个正整数，我们可以相当直接地计算结果（例如在 Javascript 中）：

function lastDigit(n, p) {
    var d = n % 10;
    return [d, (d*d)%10, (d*d*d)%10, (d*d*d*d)%10][(p-1) % 4];
}

..或更简单地说：

function lastDigit(n, p) {
    return Math.pow(n % 10, (p-1) % 4 + 1) % 10;
}

lastDigit(3, 2011)
/* 7 */

第二个函数相当于第一个函数。请注意，即使它使用幂运算，它也不会处理大于 9 的四次方 (6561) 的数字。

We can start by inspecting the last digit of each result obtained by raising the base 10 digits to successive powers:

d      d^2    d^3    d^4    d^5    d^6    d^7    d^8    d^9 (mod 10)
---    ---    ---    ---    ---    ---    ---    ---    ---
0      0      0      0      0      0      0      0      0
1      1      1      1      1      1      1      1      1
2      4      8      6      2      4      8      6      2
3      9      7      1      3      9      7      1      3
4      6      4      6      4      6      4      6      4
5      5      5      5      5      5      5      5      5
6      6      6      6      6      6      6      6      6
7      9      3      1      7      9      3      1      7
8      4      2      6      8      4      2      6      8
9      1      9      1      9      1      9      1      9

We can see that in all cases the last digit cycles through no more than four distinct values. Using this fact, and assuming that n is a non-negative integer and p is a positive integer, we can compute the result fairly directly (e.g. in Javascript):

function lastDigit(n, p) {
    var d = n % 10;
    return [d, (d*d)%10, (d*d*d)%10, (d*d*d*d)%10][(p-1) % 4];
}

... or even more simply:

function lastDigit(n, p) {
    return Math.pow(n % 10, (p-1) % 4 + 1) % 10;
}

lastDigit(3, 2011)
/* 7 */

The second function is equivalent to the first. Note that even though it uses exponentiation, it never works with a number larger than nine to the fourth power (6561).

回复收藏 0 原文

云淡月浅 2024-12-08 23:26:02

解决这类问题的关键在于欧拉定理。

这个定理允许我们说 a^phi(m) mod m = 1 mod m，当且仅当 a 和 m 互质。也就是说，a 和 m 不能被整除。如果是这种情况（对于您的示例来说就是这样），我们可以在纸上解决问题，而无需任何编程。

让我们求解 3^2011 的个位数，如您的示例所示。这相当于 3^2011 mod 10。

第一步是检查 3 和 10 是否互质。它们不能被均匀划分，所以我们可以使用欧拉定理。

我们还需要计算 10 时的 totient 或 phi 值。对于 10 ，它是 4。对于 100 phi 来说是 40，1000 是 4000 等等。

使用欧拉定理，我们可以看到 3^4 mod 10 = 1。然后我们可以将原始示例重写为：

3^2011 mod 10 = 3^(4*502 + 3) mod 10 = 3^(4*502) mod 10 + 3^3 mod 10 = 1^502 * 3^3 mod 10 = 27 mod 10 = 7

因此，3^2011 的最后一位数字是 7。

如您所见，这不需要任何编程，我在一张草稿纸上解决了这个示例。

The key to solving this type of question lies in Euler's theorem.

This theorem allows us to say that a^phi(m) mod m = 1 mod m, if and only if a and m are coprime. That is, a and m do not divide evenly. If this is the case, (and for your example it is), we can solve the problem on paper, without any programming what so ever.

Let's solve for the unit digit of 3^2011, as in your example. This is equivalent to 3^2011 mod 10.

The first step is to check is 3 and 10 are co-prime. They do not divide evenly, so we can use Euler's theorem.

We also need to compute what the totient, or phi value, is for 10. For 10, it is 4. For 100 phi is 40, 1000 is 4000, etc.

Using Euler's theorem, we can see that 3^4 mod 10 = 1. We can then re-write the original example as:

3^2011 mod 10 = 3^(4*502 + 3) mod 10 = 3^(4*502) mod 10 + 3^3 mod 10 = 1^502 * 3^3 mod 10 = 27 mod 10 = 7

Thus, the last digit of 3^2011 is 7.

As you saw, this required no programming whatsoever and I solved this example on a piece of scratch paper.

回复收藏 0 原文

没︽人懂的悲伤 2024-12-08 23:26:02

你们把简单的事情变得复杂了。

假设你想找出 abc ^ xyz 的个位数字。

divide the power xyz by 4,if remainder is 1 ans is c^1=c.
 if xyz%4=2 ans is unit digit of  c^2.
 else if xyz%4=3 ans is unit digit of  c^3.

 if xyz%4=0 
 then we need to check whether c is 5,then ans is 5
  if c is even ans is 6
 if c is odd (other than 5 ) ans is 1.

You ppl are making simple thing complicated.

Suppose u want to find out the unit digit of abc ^ xyz .

divide the power xyz by 4,if remainder is 1 ans is c^1=c.
 if xyz%4=2 ans is unit digit of  c^2.
 else if xyz%4=3 ans is unit digit of  c^3.

 if xyz%4=0 
 then we need to check whether c is 5,then ans is 5
  if c is even ans is 6
 if c is odd (other than 5 ) ans is 1.

回复收藏 0 原文

看海 2024-12-08 23:26:02

下面是一个表格，其中包含幂和 3 的个位数。
0 1
1 3
2 9
3 7
4 1
5 3
6 9
7 7

使用此表，您可以看到个位数可以是 1, 3, 9, 7，并且序列按此顺序重复以获得 3 的更高幂。使用此逻辑，您可以发现 (3 power 2011) 是 7。您可以对一般情况使用相同的算法。

回复收藏 0 原文

清醇 2024-12-08 23:26:02

这里有一个技巧，适用于不是基数因子倍数的数字（对于基数 10，它不能是 2 或 5 的倍数。）让我们使用基数 3。您想要找到的是3^2011 mod 10。从 3^1 开始，查找 3 的幂，直到找到最后一位数字 1。对于 3，您将得到 3^4=81。将原功率写为(3^4)^502*3^3。使用模算术，(3^4)^502*3^3 与 1^502*3^3 全等（最后一位数字相同）。因此 3^2011 和 3^3 具有相同的最后一位数字，即 7。

这里有一些伪代码来一般性地解释它。这将找到 b^n 在基数 B 中的最后一位数字。

// Find the smallest power of b ending in 1.
i=1
while ((b^i % B) != 1) {
    i++
}
// b^i has the last digit 1

a=n % i
// For some value of j, b^n == (b^i)^j * b^a, which is congruent to b^a
return b^a % B

如果 b 的幂均不以 1 结尾，则需要小心防止无限循环（在基数 10 中，2 或 5 的倍数不起作用。）

Here's a trick that works for numbers that aren't a multiple of a factor of the base (for base 10, it can't be a multiple of 2 or 5.) Let's use base 3. What you're trying to find is 3^2011 mod 10. Find powers of 3, starting with 3^1, until you find one with the last digit 1. For 3, you get 3^4=81. Write the original power as (3^4)^502*3^3. Using modular arithmetic, (3^4)^502*3^3 is congruent to (has the same last digit as) 1^502*3^3. So 3^2011 and 3^3 have the same last digit, which is 7.

Here's some pseudocode to explain it in general. This finds the last digit of b^n in base B.

// Find the smallest power of b ending in 1.
i=1
while ((b^i % B) != 1) {
    i++
}
// b^i has the last digit 1

a=n % i
// For some value of j, b^n == (b^i)^j * b^a, which is congruent to b^a
return b^a % B

You'd need to be careful to prevent an infinite loop, if no power of b ends in 1 (in base 10, multiples of 2 or 5 don't work.)

回复收藏 0 原文

宣告ˉ结束 2024-12-08 23:26:02

找出本例中的重复集，它是 3,9,7,1 并且它永远以相同的顺序重复......所以将 2011 除以 4 这会给你一个提醒 3这是重复集中的第三个元素。这是查找任何给定编号的最简单方法。如果要求 3^31，那么 31/4 的余数就是 3，所以 7 就是个位数字。对于 3^9，9/4 是 1，因此单位将为 3。3^100，单位将为 1。

回复收藏 0 原文

云裳 2024-12-08 23:26:02

如果你将数字和指数分开，那就很容易了。

令 n1 为数字，n2 为幂。而**代表权力。

假设n1＞0。

% 表示模除法。

伪代码如下所示

def last_digit(n1, n2)
  if n2==0 then return 1 end
  last = n1%10
  mod = (n2%4).zero? ? 4 : (n2%4)
  last_digit = (last**mod)%10
end

解释：

我们只需要考虑数字的最后一位，因为它决定了幂的最后一位。
这是数学属性，每个数字（0-9）幂的最后一位数字的可能性最多为 4。

1) 现在，如果指数为零，我们知道最后一位数字将为 1。

2) 按 %10 获取最后一位数字在数字 (n1) 上

3) %4 在指数 (n2) 上 - 如果输出为零，我们必须将其视为 4，因为 n2 不能为零。如果 %4 非零，我们必须考虑 %4 值。

4）现在我们最多有9**4。这对于计算机来说很容易计算。
取该数字的%10。你有最后一个数字。

If you have the number and exponent separate it's easy.

Let n1 is the number and n2 is the power. And ** represents power.

assume n1>0.

% means modulo division.

pseudo code will look like this

def last_digit(n1, n2)
  if n2==0 then return 1 end
  last = n1%10
  mod = (n2%4).zero? ? 4 : (n2%4)
  last_digit = (last**mod)%10
end

Explanation:

We need to consider only the last digit of the number because that determines the last digit of the power.
it's the maths property that count of possibility of each digits(0-9) power's last digit is at most 4.

1) Now if the exponent is zero we know the last digit would be 1.

2) Get the last digit by %10 on the number(n1)

3) %4 on the exponent(n2)- if the output is zero we have to consider that as 4 because n2 can't be zero. if %4 is non zero we have to consider %4 value.

4) now we have at most 9**4. This is easy for the computer to calculate.
take the %10 on that number. You have the last digit.

回复收藏 0 原文

~没有更多了~