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

在C语言中，我们可以使用递归算法结合快速幂（Fast Exponentiation）的思想来计算大整数的幂并取模1003。这个过程通常避免了直接递归导致栈溢出的问题，通过分治策略将指数不断缩小。

以下是递归函数的基本思路：

1. 定义一个递归函数pow_mod(x, n)，输入为底数x和指数n。
2. 如果n为0，返回1，因为任何数的0次幂都是1，并且1003的乘法运算对结果取模无影响。
3. 如果n为正偶数，将x平方并除以1003（即x * x % 1003），然后递归计算(n / 2)次幂。
4. 如果n为奇数，先计算x的一半的n次幂，再将结果乘以x（即pow_mod(x, (n - 1) / 2) * x % 1003）。
5. 返回上述步骤的结果。

这是一个简单的伪代码示例：

int pow_mod(int x, int n) {
    if (n == 0) return 1;
    int half_n = n >> 1; // 取n的一半，假设n为非负整数

    int temp = pow_mod(x, half_n); // 计算half_n次幂
    if (n % 2) { // 如果n是奇数
        return (temp * x) % 1003; // 加上剩余的一半
    } else {
        return (temp * temp) % 1003; // 因为n是偶数，所以是平方
    }
}

// 示例调用
int result = pow_mod(2, 10);