数据结构高次幂运算问题

Problem Description
计算 a 的 b 次方对 1e9+7 取模以后的结果。

输入
两个超大正整数 a 和 b。(1 <= a，b <= 1e100)

输出
a 的 b 次方对 1e9+7 取模以后的结果，然后换行。

样例输入
2 10
样例输出
1024

用数组来存储结果

#include<stdio.h>
#define MOD 1000000007
int main()
{
    int arr[1000] = {0};    //用于存放计算的数据，初始化为0
    arr[999] = 1;    //最初：数组最后一个元素定义为1
    int i = 0;
    int N = 0;//底数
    int M = 0;//指数
    scanf("%d %d",&N,&M);
    //有1000个元素，最后一个元素下标为：999
    for(i = 0 ;i < M;i++)
    {
        int j = 0;
        for(j = 999;j>=0;j--)
        {
            arr[j] *=N;    //数组中的每一位元素都乘以底数
            //最初只有数组最后一位乘了，因为其他位全为0
        }
         for(j = 999;j>=0;j--)
         {
             //如果数组中的元素大于等于10就进位，把余数放到本身，商放到上一个位置
             if(arr[j] >= 10)
             {
                 arr[j-1] += arr[j]/10;//商进位到上一个位置
                 arr[j] = arr[j] %10;//本身位置取余数
             }
         }
    }
    //最后遍历数组找到数组元素第一个不为0的位置
    int index = 0;
      for (i = 0; i < 1000; i++)
      {
         if (arr[i] == 0 && arr[i + 1] != 0)
        {
             //i+1位置元素不为0
            index = i + 1;
            break;
        }
      }
      int mod = 0;
  for (int i = 0; i < 1000; i++) {
    mod = (mod * 10 + arr[i]) % MOD;
  }
  printf("%d\n", mod);
    
    return 0;
}

比较简单但可能会超时的：
重复b次:
a*a再把它对1e9+7曲模
这样避免了数据过大的情况
b可以用字符串char数组存储

这里

这道题可以使用快速幂算法来解决。

使用 C++ 实现的快速幂算法如下：

#include <iostream>

using namespace std;

// 计算 a 的 b 次方对 m 取模的结果
long long fast_pow(long long a, long long b, long long m) {
    a %= m;
    long long result = 1;
    while (b > 0) {
        if (b & 1) {
            result = result * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return result;
}

int main() {
    long long a = 2, b = 10, m = 1e9 + 7;
    cout << fast_pow(a, b, m) << endl;
    return 0;
}

在这里，我们使用了 long long 类型来存储超大正整数，并且在每一步计算之后取模，以防结果太大导致溢出。

# include <stdio.h>
# include <string.h>
# include <stdlib.h>

# define MOD 1000000007

char a[1000005]
char b[1000005]

// 将字符串转为长整型
long long toLong(char * str) {
    long long res = 0
    for (int i=0
         i < strlen(str)
         i++) {
        res = res * 10 + str[i] - '0'
    }
    return res
}

// 将长整型转为字符串
char * toString(long long x) {
    char * str = (char*)malloc(sizeof(char) * 1000005)
    int i = 0
    while (x > 0) {
        str[i++] = x % 10 + '0'
        x /= 10
    }
    str[i] = '\0'
    return str
}

// 快速幂
long long quickPower(long long a, long long b) {
    long long res = 1
    while (b > 0) {
        if (b & 1) {
            res = res * a % MOD
        }
        a = a * a % MOD
        b >>= 1
    }
    return res
}

int main() {
    scanf("%s %s", a, b)

    long long x = toLong(a)
    long long y = toLong(b)

    char * res = toString(quickPower(x, y))
    printf("%s\n", res)

    return 0
}

#include <stdio.h>
#include <string.h>

#define MOD 1000000007

// 超大数组，用于存储超大数
int num[10000];

// 超大数乘法
void multiply(int *num, int len, int x) {
    int carry = 0;
    for (int i = 0; i < len; i++) {
        int result = num[i] * x + carry;
        num[i] = result % 10;
        carry = result / 10;
    }
}

// 超大数乘方
void power(int *num, int len, int x) {
    int result[10000] = {1};
    int result_len = 1;

    // 计算 a 的 b 次方
    while (x) {
        if (x & 1) {
            multiply(result, result_len, num[0]);
            result_len += (result[result_len - 1] == 0);
        }
        multiply(num, len, num[0]);
        len += (num[len - 1] == 0);
        x >>= 1;
    }

    // 对 1e9+7 取模
    memcpy(num, result, result_len * sizeof(int));
    len = result_len;
    while (len > 0 && num[len - 1] == 0) {
        len--;
    }
}

下面C语言代码可以计算 a 的 b 次方对 1e9+7 取模以后的结果，望采纳

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOD 1000000007

char a[10001];
char b[10001];
int c[10001];

int main() {
  scanf("%s%s", a, b);

  // 先计算 a^b
  int len_a = strlen(a);
  int len_b = strlen(b);
  for (int i = 0; i < len_a; i++) {
    c[i] = a[len_a - 1 - i] - '0';
  }
  int len_c = len_a;
  for (int i = 1; i < len_b; i++) {
    int carry = 0;
    for (int j = 0; j < len_c; j++) {
      c[j] = c[j] * 2 + carry;
      carry = c[j] / 10;
      c[j] %= 10;
    }
    while (carry) {
      c[len_c++] = carry % 10;
      carry /= 10;
    }
  }

  // 再计算 a^b % MOD
  int mod = 0;
  for (int i = 0; i < len_c; i++) {
    mod = (mod * 10 + c[i]) % MOD;
  }
  printf("%d\n", mod);

  return 0;
}

输入样例：

2 10

输出样例：

1024