如何找出某个数字（例如3的2011次方）的个位数字？我应该使用什么逻辑来解决这个问题？
如何以最简单的方式找到某个幂的个位数
10
- user915435
3
你使用的是哪种编程语言？ - Javed Akram
5这与语言无关，我只是想找出最简单的解决方法。我只对这个非常大的数字的个位数感兴趣，不一定需要答案。 - user915435
将“pseudocode”标签添加到此处...这个链接对你有帮助吗？ - DaveRandom
10个回答
21
对于基数为3：
3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
...
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（它是该特定数字的起始偏移量） - 对指数取模 4 => :=
off（根据欧拉定理，我们只有四个可能的结果！） - 将
off添加到4*i以获得结果
现在为了使其尽可能有效率，应用了一些基本算术运算的调整：
- 乘以 4 等同于向左移动两位（'<< 2'）
- 对一个数
a % 4可以等同于a&3（屏蔽掉形成余数 % 4 的第 1 位和第 2 位）
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互质（即它们的最大公约数等于1）的数字。小于10且与10互质的数字是1、3、7和9。因此，phi(10) = 4，这证明了确实 a^4 mod 10 = 1 mod 10。
最后需要证明的是，对于以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整除。
- emboss
2
2它对于任何任意进制都是一样的。只需将其截断到最后一位数字并应用相同的算法即可。 - aroth
这些问题在GRE考试中经常出现，这个答案比我在任何学习指南中看到的都要好。非常感谢Stack Overflow。 - David Kelley
8
你应该查看模幂运算。你想要的是计算n^e (mod m)，其中m = 10。这与计算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
接着，只需使用模数为10的你所需的基数和指数进行调用，就可以得到你的答案。
编辑：对于一种更简单的方法，CPU效率较低但内存效率更高，请查看维基百科文章中的内存高效部分。逻辑足够直观：
function modular_pow(base, exponent, modulus)
c := 1
for e_prime = 1 to exponent
c := (c * base) mod modulus
return c
- Rafael Almeida
8
我相信有一种适当的数学方法来解决这个问题，但我建议你只关注最后一位数字，而且理论上每个数不断地乘以自己最终应该会生成一个重复的模式（仅考虑最后一位），因此你可以执行乘法直到检测到第一个重复，然后将指数映射到你构建的模式中的适当位置。
请注意，因为你只关心最后一位数字，你可以通过将输入数字截断到它的个位数来进一步简化。这将让你确定最后一位数字，即使是对于可能在第一或第二次乘法中导致溢出的任意大的输入也可以实现。
以下是JavaScript的基本示例：http://jsfiddle.net/dtyuA/2/
顺带一提，
请注意，因为你只关心最后一位数字，你可以通过将输入数字截断到它的个位数来进一步简化。这将让你确定最后一位数字，即使是对于可能在第一或第二次乘法中导致溢出的任意大的输入也可以实现。
以下是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。- aroth
10
1这基本上就是解决它的正确数学方法。 - Tom Zych
1哎呀。很快你就会整夜研究证明定理，思考黎曼ζ函数，甚至可能玩围棋。不久之后，你会变成一个语无伦次的傻子，喃喃自语着拉普拉斯变换和三重积分。趁你还能逃跑的时候赶紧离开吧！ - Tom Zych
@Rafael，你的回答没有涉及到检测周期并快速计算答案的美妙想法。与你的情况中的
log(e)不同，这个方法实际上给出了O(m)。至少在n和m互质的情况下是如此。 - unkulunkulu@unkulunkulu，你说得对。将模数设置为10可以让你应用多种优化。我的回答基本上是从另一个角度看问题，我承认这种方法在教学上更有趣，但在实际/高效的方式上可能不太适用。 - Rafael Almeida
@Rafael，即使模数不是10，你也可以检测到周期，我是想这么说的。但是你的方法编码容易，并且速度还算可以，当然，我只是说说而已 :D - unkulunkulu
显示剩余5条评论
3
我们可以从检查将基数 10 的数字连续乘方所得到结果的末位开始：
我们可以看到，在所有情况下，最后一位数字循环不超过四个不同的值。利用这一点，假设
第二个函数和第一个等价。请注意，即使它使用指数运算，它也永远不会处理大于九的四次方（6561）的数字。
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 */
第二个函数和第一个等价。请注意，即使它使用指数运算，它也永远不会处理大于九的四次方（6561）的数字。
- WReach
2
在你的第二个函数中，为什么要做 n % 10？ - samoz
@samoz
n % 10 使得该函数适用于多位数。如果输入限制为单个数字，则不必要。 - WReach3
解决这种类型问题的关键在于欧拉定理。
该定理允许我们说，如果a和m互质，则a^phi(m) mod m = 1 mod m。也就是说，a和m不能被平均分割。如果是这种情况（对于你的例子而言是这样），我们可以在纸上解决问题，无需任何编程。
让我们解决3^2011的个位数，就像你的例子一样。这相当于求3^2011 mod 10。
第一步是检查3和10是否互质。它们不能被平均分割，因此我们可以使用欧拉定理。
我们还需要计算10的欧拉函数或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。
正如您所看到的，这并不需要任何编程，我是在一张草稿纸上解决了这个问题。
- samoz
1
1欧拉定理加1。如果你利用它并预先计算2、3和7的四个可能值，你甚至可以比这更快地完成它（请参见我的尝试）。 - emboss
1
你们把简单的事情复杂化了。
假设你想要找到 abc ^ xyz 的个位数。
假设你想要找到 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.
- user1112782
0
这里有一个技巧，适用于不是基数因子倍数的数字（对于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进制下b^n的最后一位。
// 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结尾（在十进制中，2或5的倍数不起作用），则需要小心防止无限循环。
- user916576
0
找出这个序列中的重复集合，即3,9,7,1，并且按照相同的顺序无限循环……因此将2011除以4得到余数3。这是重复集合中的第3个元素。这是查找任何给定数字的最简单方法。例如，如果要求3^31，则31/4的余数为3，因此个位数为7。对于3^9，9/4为1，因此个位数为3。对于3^100，个位数将为1。
- siva
0
下面是一个表格，列出了3的幂次方及其个位数。
0 1
1 3
2 9
3 7
4 1
5 3
6 9
7 7
通过这个表格，您可以看到单位数可以是1、3、9、7，而且这个序列会按照这个顺序重复出现。使用这个逻辑，您可以发现(3的2011次方)的个位数是7。对于一般情况，您可以使用相同的算法。
0 1
1 3
2 9
3 7
4 1
5 3
6 9
7 7
通过这个表格，您可以看到单位数可以是1、3、9、7，而且这个序列会按照这个顺序重复出现。使用这个逻辑，您可以发现(3的2011次方)的个位数是7。对于一般情况，您可以使用相同的算法。
- Andrei Bozantan
0
如果您将数字和指数分开，这将变得很容易。
假设n1是数字，n2是幂。
假设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）通过对数字(n1)进行%10运算获取最后一位。
3）对指数(n2)进行%4运算——如果输出为零，我们必须将其视为4，因为n2不能为零。如果%4不为零，则必须考虑%4的值。
4）现在我们最多有9 ** 4。这对计算机来说很容易计算。对该数字进行%10运算。您就得到了最后一位。
- InQusitive
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接