数据结构高次幂运算问题

Question

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

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

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

样例输入
2 10
样例输出
1024

Answer 1

用数组来存储结果

#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;
}