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

在C语言中，我们可以使用循环或者模运算优化的乘法来计算给定整数x的n次幂mod 1003。这里我将演示一种基于快速幂（Fast Exponentiation）的递归算法，这种方法可以在O(log n)的时间复杂度内完成。

#include <stdio.h>

// 计算 a^b mod m 的函数，利用快速幂思想
long long power(long long a, long long b, long long m) {
    if (b == 0) return 1; // 如果指数为0，结果为1
    if (b % 2 == 1) { // 如果指数为奇数
        return (a * power(a, b - 1, m)) % m;
    } else { // 否则如果指数为偶数，先平方再除半
        long long half = power(a, b / 2, m);
        return (half * half) % m;
    }
}

int main() {
    long long x, n;
    scanf("%lld%lld", &x, &n); // 输入x和n

    // 输出x^n mod 1003
    long long result = power(x, n, 1003);
    printf("%lld\n", result);

    return 0;
}

在这个程序中，我们首先检查b是否为偶数，如果是，则将问题简化为计算a^(b/2)的平方。如果不是偶数，我们将a乘以自身n-1次，每次取模m以防止溢出。