编写程序计算 a^x mod b 的值。函数 mod(a,x,b)返回 a^x mod b的值。a和b是最多10位的整数,x是最多200位的整数,用递归方式实现。
时间: 2023-08-31 15:40:38 浏览: 49
### 回答1:
以下是使用递归方式实现 a^x mod b 的 Python 代码:
```python
def mod(a, x, b):
if x == 0:
return 1
elif x % 2 == 0:
temp = mod(a, x // 2, b)
return (temp * temp) % b
else:
temp = mod(a, x - 1, b)
return (a * temp) % b
```
该函数使用二分法递归计算 a^x mod b 的值。当指数 x 为 0 时,返回 1。当指数 x 为偶数时,先计算 a^(x/2) mod b 的值(使用递归),然后将其平方取模得到 (a^(x/2))^2 mod b 的值。当指数 x 为奇数时,先计算 a^(x-1) mod b 的值(使用递归),然后将其乘以 a 再取模得到 a^(x-1) * a mod b 的值。
可以通过以下方式调用该函数:
```python
a = 1234567890
x = 9876543210
b = 987654321
result = mod(a, x, b)
print(result)
```
其中,a、x和b分别为底数、指数和模数,result为计算结果。
### 回答2:
下面是用递归方式实现的计算 a^x mod b 的程序:
```python
def mod(a, x, b):
if x == 0:
return 1
elif x % 2 == 0:
temp = mod(a, x / 2, b)
return (temp * temp) % b
else:
temp = mod(a, (x - 1) / 2, b)
return (a * ((temp * temp) % b)) % b
# 示例
a = 5
x = 7
b = 3
result = mod(a, x, b)
print(result)
# 输出: 2
```
这个程序中,递归函数 `mod(a, x, b)` 的三个参数分别表示底数 a,指数 x,以及模数 b。程序首先判断指数 x 是否为零,如果是,则返回 1。然后判断指数 x 是否为偶数,如果是,则递归调用 `mod(a, x / 2, b)` 求解一半指数的结果 temp,然后返回 $temp^2 $ 除以模数 b 的余数。如果指数 x 是奇数,则递归调用 `mod(a, (x - 1) / 2, b)` 求解去除一位之后的指数的结果 temp,然后返回 a 乘以 $temp^2$ 除以模数 b 的余数。最终得到的结果即为 a^x mod b 的值。
在示例中,计算 5^7 mod 3 的结果为 2。