算法例6 快速幂"/>
python算法例6 快速幂
1. 问题描述
计算,其中a、b和n都是32位的非负整数。
2. 问题示例
例如:。
3.代码实现
计算a的n次幂对b取余,可以使用快速幂算法。这个算法通过减少乘法和取余操作的次数来提高效率。
def pow_mod(a, n, b):result = 1while n > 0:if n % 2 == 1: # 如果n是奇数result = (result * a) % ba = (a * a) % bn //= 2return resultprint(pow_mod(2,31,3))
在这段代码中,使用了一个循环,通过二进制位逐步减小n的值,并根据n的二进制位是否为1来更新结果。具体步骤如下:
- 初始化结果为1。
- 当n大于0时,进行循环:
- 如果n是奇数(即n的二进制表示的最低位是1),将结果与a相乘并对b取余。
- 将a自乘并对b取余。
- 将n除以2向下取整。
- 返回最终结果。
例如,对于输入a = 2
、n = 31
和b = 3
,根据快速幂算法,计算结果为2。
更多推荐
python算法例6 快速幂
发布评论