题目描述 给定整数x和n,求x的n次幂 mod 1003 输入 整数x和n。 1<=x,n<=1,000,000,0000 输出 x^n mod 1003 样例输入 2 10 样例输出 21 提示 两种方法： 1、二进制方法 2、递归算法 用python做

题目要求计算一个大整数 `x` 的 `n` 次方并对结果取模 1003。这是计算机科学中常见的大数运算问题，尤其是当 `x` 或 `n` 达到非常大的值时，直接计算会超出常规数据类型的范围。这里有两种常用的解决方案：

1. **二进制指数法则（Binary Exponentiation or Fast Exponentiation）**: 利用了指数运算的性质，通过分解指数为二的幂次相乘来避免大量的乘法。这种方法将问题转化为一系列较小的乘法运算。

   def power(x, n, modulo=1003):
       result = 1
       while n > 0:
           if n % 2 == 1:
               result = (result * x) % modulo
           x = (x * x) % modulo
           n //= 2
       return result

2. **递归算法**:
另一种方法是利用递归来实现，但是这种方式对于非常大的 `n` 可能会因为递归深度过深而导致栈溢出，所以一般不推荐。

def recursive_power(x, n, modulo=1003):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half_result = recursive_power(x, n // 2, modulo)
        return (half_result * half_result) % modulo
    else:
        half_result = recursive_power(x, (n - 1) // 2, modulo)
        return (x * (half_result * half_result)) % modulo

以上两种方法都可以有效地处理这种大数计算并保证输出正确。