c语言利用递归算法解决问题给定整数x和n,求x的n次幂 mod 1003 Input 整数x和n。 1<=x,n<=1,000,000,0000 Output x^n mod 1003 Sample Input 2 10 Sample Output 21
时间: 2024-10-17 17:10:38 浏览: 9
在C语言中,可以使用递归算法结合快速幂(Fast Exponentiation)的方式来解决这个问题。快速幂是一种优化版的指数计算方法,当n较大时,通过分治策略将原问题转化为一系列较小规模的问题,大大减少了计算量。
以下是使用递归实现的C代码片段:
```c
long long fast_pow(int x, int n, int mod) {
if (n == 0) // 当n为0时,任何数的0次方都是1
return 1;
else if (n % 2 == 0) { // 如果n是偶数,先平方再除以2
long long half = fast_pow(x, n / 2, mod);
return (half * half) % mod;
} else { // 如果n是奇数,直接计算x的n次方
long long half = fast_pow(x, (n - 1) / 2, mod);
return (x * half * half) % mod;
}
}
int main() {
int x, n;
scanf("%d%d", &x, &n); // 输入x和n
printf("%lld\n", fast_pow(x, n, 1003)); // 输出x的n次幂对1003取余的结果
return 0;
}
```
这个函数首先检查基本情况(n为0),然后根据n的奇偶性递归地调用自身,每次都将n减半或除以2,直到n变为0。这样可以避免大量的乘法运算,因为只需要进行log2(n)次乘法操作。
阅读全文