C语言输入两个数 a, b,其中 b 极大。计算 a 的 b 次方对 1337 取模的结果。数据保证 a 在 int 范围内,b 小于 100 位。
时间: 2024-03-07 11:50:49 浏览: 25
这个问题可以使用快速幂算法来解决,快速幂算法可以有效地降低计算幂的时间复杂度。
具体实现方式如下:
```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](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)