如何找出某个数字(例如3的2011次方)的个位数字?我应该使用什么逻辑来解决这个问题?
如何找出某个数字(例如3的2011次方)的个位数字?我应该使用什么逻辑来解决这个问题?
对于基数为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:
i
4*i
(它是该特定数字的起始偏移量)off
(根据欧拉定理,我们只有四个可能的结果!)off
添加到 4*i
以获得结果现在为了使其尽可能有效率,应用了一些基本算术运算的调整:
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整除。
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
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。log(e)
不同,这个方法实际上给出了O(m)
。至少在n
和m
互质的情况下是如此。 - unkulunkulud 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 */
n % 10
使得该函数适用于多位数。如果输入限制为单个数字,则不必要。 - WReach该定理允许我们说,如果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。
正如您所看到的,这并不需要任何编程,我是在一张草稿纸上解决了这个问题。
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.
这里有一个技巧,适用于不是基数因子倍数的数字(对于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的倍数不起作用),则需要小心防止无限循环。
找出这个序列中的重复集合,即3,9,7,1
,并且按照相同的顺序无限循环……因此将2011除以4得到余数3。这是重复集合中的第3个元素。这是查找任何给定数字的最简单方法。例如,如果要求3^31,则31/4的余数为3,因此个位数为7。对于3^9,9/4为1,因此个位数为3。对于3^100,个位数将为1。
** 表示幂。
假设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运算。您就得到了最后一位。