记录编号	125527	评测结果	AAAAAAAAAAAAAA
题目名称	[暑假培训2012] 残酷的数学老师	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.067 s
提交时间	2014-10-08 23:04:06	内存使用	0.31 MiB

#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef unsigned long long LL;
LL n,m;
const int MAX=10010;
struct hp
{
    LL num[MAX];
    hp() {memset(num,0,sizeof(num));num[0]=1;}
    void print()
    {
        printf("%llu",num[num[0]]);int k=10,t=1;
        while(num[num[0]]/k!=0) k*=10,t++;
        for(int i=num[0]-1;i>0;i--)
        {
            if(t+4>=70)
            {
                char s[10];
                sprintf(s,"%.4llu",num[i]);
                for(int i=0;i<70-t;i++) printf("%c",s[i]);
                printf("\n");
                for(int j=70-t;j<=3;j++) printf("%c",s[j]);
                t=t-65;
            }
            else printf("%.4llu",num[i]),t+=5;
        }
    }
};

hp operator * (hp a, LL b)
{
    int len=2*a.num[0];int i;
    for(i=1;i<=len;i++) a.num[i]*=b;
    for(i=1;i<=len;i++)
    {
        if(a.num[i]>=10000)
        {
            a.num[i+1]+=a.num[i]/10000;
            a.num[i]%=10000;
        }
    }
    while(a.num[a.num[0]]==0&&a.num[0]>1) a.num[0]--;
    while(a.num[a.num[0]+1]>0) a.num[0]++;
    return a;
}

hp operator * (hp a,hp b)
{
    hp c;c.num[0]=a.num[0]+b.num[0];
    for(int i=1;i<=a.num[0];i++)
    {
        for(int j=1;j<=b.num[0];j++)
        {
            c.num[i+j-1]+=a.num[i]*b.num[j];
        }
    }
    for(int i=1;i<=c.num[0];i++)
    {
        if(c.num[i]>=10000)
        {
            c.num[i+1]+=c.num[i]/10000;
            c.num[i]%=10000;
        }
    }
    while(c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--;
    return c;
}

hp power(LL a,LL b)
{
    if(b==0) {hp t;t.num[1]=1;return t;}
    if(b==1)
    {
        hp t;int len=1,k=1;
        while(a>0)
        {
            if(k>=10000) {k=1;len++;}
            t.num[len]+=k*(a%10);
            k*=10;a/=10;
        }
        t.num[0]=len;
        return t;
    }
    hp t=power(a,b/2);
    t=t*t;
    if(b%2==1) t=t*a;
    return t;
}

int main()
{
    freopen("cruel1.in","r",stdin);
    freopen("cruel1.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    hp c=power(n,m);
    c.print();
    return 0;
}