输入两个数 a, b,其中 b 极大。计算 a 的 b 次方对 1337 取模的结果。数据保证 a 在 int 范围内,b 小于 100 位。
时间: 2023-07-14 17:14:21 浏览: 87
这是一道快速幂取模的题目,先介绍一下快速幂的算法。
快速幂算法是通过对指数进行二进制分解来达到快速计算幂次的目的,这个算法的时间复杂度是 O(log2 n)。
算法的思想是:将指数表示成二进制,如 $b = 11_2 = 1\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0$ ,那么 $a^b = a^{2^3} \times a^{2^1} \times a^{2^0}$ 。这里用到了一个性质:$a^{b+c} = a^b \times a^c$。
在取模的情况下,对于一个数 $x$,我们有 $x^b \bmod m = (x \bmod m)^b \bmod m$。
下面是代码实现:
```python
def pow_mod(a: int, b: str, m: int) -> int:
"""
计算 a 的 b 次方对 m 取模的结果
"""
a %= m
res = 1
for i in range(len(b)-1, -1, -1):
if b[i] == '1':
res = res * a % m
a = a * a % m
return res
```
其中,参数 `a` 是底数,`b` 是字符串形式的指数,`m` 是模数。
相关问题
C语言输入两个数 a, b,其中 b 极大。计算 a 的 b 次方对 1337 取模的结果。数据保证 a 在 int 范围内,b 小于 100 位。
这个问题可以使用快速幂算法来解决,快速幂算法可以有效地降低计算幂的时间复杂度。
具体实现方式如下:
```c
int superPow(int a, int* b, int bSize){
if (bSize == 0) return 1;
int last = b[bSize - 1];
int part1 = myPow(a, last);
int part2 = myPow(superPow(a, b, bSize - 1), 10);
return (part1 * part2) % 1337;
}
int myPow(int a, int k) {
a %= 1337;
int res = 1;
for (int i = 0; i < k; i++) {
res *= a;
res %= 1337;
}
return res;
}
```
其中,`superPow` 函数用来计算 a 的 b 次方对 1337 取模的结果,`myPow` 函数用来计算 a 的 k 次方对 1337 取模的结果。
在 `superPow` 函数中,首先判断 b 是否为空,如果为空则直接返回1;否则,分别计算 a 的最后一位和前面的数,然后使用递归计算前面的数,最后将两部分的结果相乘并对 1337 取模即可。
在 `myPow` 函数中,使用循环计算 a 的 k 次方,每次计算后都对 1337 取模。
需要注意的是,在计算 a 的最后一位时,需要将 b 数组的最后一位赋值给 `last` 变量,而不是直接使用 `b[bSize - 1]`,因为指针的值是可以改变的。
c语言解决:输入两个数a,b,求a的b次方的最后一位
可以使用快速幂算法来求解,具体实现如下:
```c
#include <stdio.h>
int quick_pow(int a, int b) {
int res = 1 % 10;
while (b) {
if (b & 1) {
res = res * a % 10;
}
a = a * a % 10;
b >>= 1;
}
return res;
}
int main() {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", quick_pow(a, b));
return 0;
}
```
注意:这里计算过程中每次要对结果取模,否则可能会发生整型溢出,导致结果错误。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)