C语言输入两个数 a, b,其中 b 极大。计算 a 的 b 次方对 1337 取模的结果。数据保证 a 在 int 范围内,b 小于 100 位。
时间: 2024-03-07 07:50:49 浏览: 56
C语言实验-有3个整数a,b,c,由键盘输入,编写程序输出其中绝对值最大(或最小)的数。
5星 · 资源好评率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]`,因为指针的值是可以改变的。
阅读全文