2021-08-29

Pow(x, n)%10 (快速幂+大数取模问题)

题目描述

来自:Zoom2021年秋招前端工程师笔试编程题2

给定2个非负整数x, n, 需要求 x^n (x的n次方)的最后一位。 x, n都可能很大很大。

任何数的0次方都是1.

分析

思路1

不难发现规律: ((x%y)^n)%y = (x^n)%y

因此很容易想到,第一步先把题目中的底数x提取成最后一位。但如果直接用编程语言库里自带的Math.pow(x, n),依然可能会直接得到一个很大的结果,取模依然可能不正确。因此,我们需要考虑自己实现一套幂运算,在过程中多次取最后一位,这样就会使得所有的运算都是小数取模了。

快速幂公式参考LeetCode 50. Pow(x, n) (快速幂,清晰图解)-Krahets

思路2

根据观察不难发现,0-9为底的幂运算取最后一位是存在一个循环的。我们先求出这个循环的规律,然后判断n是在循环的第几位,即可直接得到结果。

注意

由于Javascript BigInt过于复杂,没有实现x, y为大数时的算法。

代码

公用方法.js
1
2
3
function mod10( num ) {
return parseInt(num) % 10;
}
思路1.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function lastDigitQuickPow(str1, str2) {
let x = mod10(str1); // x直接取最后一位
let n = parseInt(str2); // 可能涉及大数,转成BigInt
if (n === 0) {
return 1; // 任何数的0次方都是1
}
let res = 1;
for (let i = x; n; i = mod10(i * i), n = n >> 1) {
// 每次使i平方,然后n减少一位二进制位(位右移)
if ((n & 1) == 1) {
res = mod10(res * i); // 如果当前位是1,则在结果中增加
}
}
return res;
}
思路2.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function lastDigit(str1, str2) {
let x = mod10(str1); // x直接取最后一位
let n = parseInt(str2); // 可能涉及大数,转成BigInt
if (n === 0) {
return 1; // 任何数的0次方都是1
}
let loopCount = 0;
let loopNum = [x];
for (let i = x; true;) {
i = mod10(i * x); // 查找循环的下一位
loopCount++;
if (i === x) {
break; // 得到循环的总长度loopCount和取余对应loopNum[]
} else {
loopNum.push(i);
}
}
let resMod = (n - 1) % loopCount; // 获取循环中的余数(左移一位)
return loopNum[resMod];
}