幂运算精确值计算问题

来源

http://139.196.145.92/contest_show.php?cid=1895#problem/B

Description

输入两个不超过10000的正整数a、n正整数n，输出a^n的精确结果。

Input

本问题有多组测试数据，对于每一组测试数据，只有一行，每行有用空格隔开的两个正整数。

Output

对于每一组测试数据，输出只有一行，即计算的结果。

Sample Input

2 3
91 37

Sample Output

8
3051627471597949451463369059654147285577479747909625754790616546501477931

分析问题:

注意两个表述的区别
- 两个加数的位数不超过100000位(另外一个题):需要用一个数组存储
- 两个不超过10000的正整数a,n:int变量直接存储
对于(a^b)这样一个算式,我们一共需要计算b次.每一轮计算我们都能获得一个暂时的值名为ans,ans的初始值为1.每次计算(ans*a),我们依次让a乘以ans的每一位,计算的结果记为temp,然后让temp%10,表示ans当前位最后应该留下的值,同时使temp/10求得对于下一位的进位,记为carry.依次确保a和ans的每一位如此操作即可.

注意:carry在每一轮的初值应为0,每次计算a乘以ans的某一位时都还需要加上carry
时间复杂度:(b*ans的长度=10000*(1,40001))

解释一下ans的最大长度:(10000^{10000} -> (lg(10)=4) -> 40000+1)

由于从1到40001是近似线性增长的,我们可以取一个中间数20000,则大致的时间复杂度为200000000,约2s

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 40010;
int ans[N];

int main()
{
    int a,b;
    while(scanf("%d %d",&a,&b)!=EOF){
        int maxx=0;
        memset(ans,0,sizeof ans);
        ans[0]=1;
        while(b--){
            int carry=0,temp,now=0;
            while(true){
                //这里用了true是因为没有办法直接判断退出循环的时机
                temp=carry;
                if(now<=maxx){
                    temp += a*ans[now];  //考虑一下什么时候可以乘:当now<=maxx的时候
                    ans[now]=temp%10;
                    carry=temp/10;
                }else{
                    //考虑出口:当now>maxx同时carry=0的时候显然可以考虑出去了
                    if(!carry){
                        break;
                    }
                    ans[now]=temp%10;
                    carry=temp/10;
                }
                now++;
            }
            maxx=now;
        }
        //注意输出
        bool flag=1;
        for(int i=maxx;i>=0;i--){
            if(flag&&ans[i]){
                flag=0;
                printf("%d",ans[i]);
            }else if(!flag){
                printf("%d",ans[i]);
            }
        }
        if(flag){
            printf("0");
        }
        printf("
");
    }
    return 0;
}