查找 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