查找 a^b 最后一位数字的最有效方法
Most efficient way to find the last digit of a^b
我是 python 新手。我希望以最有效的方式计算 (a ** b) % 10（即简化电源部分）。我找到了一种方法：((a % 10) ** b) % 10。我的问题是，是否有更有效的方法来做到这一点？此问题是 CodeFights 任务的扩展。原题接受(a ** b) % 10.
因为数mod10形成一个ring，可以计算余数mod 10 在每个中间值而不影响结果。
有一种名为 Square-and-multiply 的 O(log b) 步算法可以大大加快您的计算速度。
基本思路是，即使是 b，我们也可以将参数平方
并在不改变结果的情况下将指数除以 2。
对于奇数 b，我们提取 a 的一次幂（或我们当前的参数）并像在偶数情况下一样进行（平方和减半）。
所以把这些放在一起，如果你实现平方和乘法算法并在每一步之后计算残差 mod 10，你将得到一个很好的计算最后一位数字的有效方法。
- 第 1 步： 获取输入 a 和 b 作为字符 string
- 第 2 步：
- 仅将 a 的最后一个字符转换为 integer 并存储在变量中 say m.
- 仅将b的最后两个字符转换为整数并存储在变量中说 n。
如果b是单个字符，那么只转换这个字符。
- 第 3 步： 找到 x。
if n % 4 == 0:
x = 4
else:
x = n % 4
- 第 4 步：
last_digit = (m ** x) % 10
简短说明：
如果你列出一个幂的初始扩展，你会发现一个模式。
所以我们可以将 a 和 b 减少到 m 和 x 分别。
因为它只是最后一位数字。
您可以访问：this site for the better explanation to find out last digit of a^b
我是 python 新手。我希望以最有效的方式计算 (a ** b) % 10（即简化电源部分）。我找到了一种方法：((a % 10) ** b) % 10。我的问题是，是否有更有效的方法来做到这一点？此问题是 CodeFights 任务的扩展。原题接受(a ** b) % 10.
因为数mod10形成一个ring，可以计算余数mod 10 在每个中间值而不影响结果。
有一种名为 Square-and-multiply 的
O(log b)步算法可以大大加快您的计算速度。基本思路是，即使是
b，我们也可以将参数平方 并在不改变结果的情况下将指数除以 2。 对于奇数b，我们提取a的一次幂（或我们当前的参数）并像在偶数情况下一样进行（平方和减半）。
所以把这些放在一起，如果你实现平方和乘法算法并在每一步之后计算残差 mod 10，你将得到一个很好的计算最后一位数字的有效方法。
- 第 1 步： 获取输入 a 和 b 作为字符 string
- 第 2 步：
- 仅将 a 的最后一个字符转换为 integer 并存储在变量中 say m.
- 仅将b的最后两个字符转换为整数并存储在变量中说 n。 如果b是单个字符，那么只转换这个字符。
- 第 3 步： 找到 x。
if n % 4 == 0: x = 4 else: x = n % 4 - 第 4 步：
last_digit = (m ** x) % 10
简短说明： 如果你列出一个幂的初始扩展，你会发现一个模式。 所以我们可以将 a 和 b 减少到 m 和 x 分别。 因为它只是最后一位数字。
您可以访问：this site for the better explanation to find out last digit of a^b