给出三个整数 a,b,m ,求 abmodm 的值。
时间: 2024-05-10 21:21:04 浏览: 104
可以使用快速幂算法来求解。
首先,将 b 表示成二进制形式,例如:b=101101,那么:
a^b = a^(2^5) * a^(2^4) * a^(2^2) * a^(2^1)
也就是说,将 b 用二进制表示后,每一位上的1对应着 a 的不同次幂,我们只需要计算出这些次幂对应的值,然后相乘即可。
具体实现可以使用一个循环,每次将 a 的次幂平方,然后检查 b 的当前二进制位是否为1,如果为1,则将结果乘上当前次幂值,最后将结果对 m 取模即可。
以下是具体的代码实现:
```python
def quick_pow(a, b, m):
res = 1
a %= m
while b:
if b & 1:
res = res * a % m
a = a * a % m
b >>= 1
return res
```
其中,a 表示底数,b 表示指数,m 表示模数。运行时间复杂度为 O(log b)。
阅读全文