USACO 2009 Feb Cruel Math Teacher 数的幂次

USACO 2009 Feb Cruel Math Teacher 数的幂次

快速幂，不多说了。

#include<cstdio>
#include<cstring>
int a[15001],b[15001],c[15001],n,p;void copy(int c[],int a[])
{for(int i=0;i<=c[0];i++)a[i]=c[i];
}void mutil(int a[],int b[],int c[])
{for(int i=0;i<=a[0]+b[0];i++)c[i]=0;for(int i=1;i<=a[0];i++){for(int j=1;j<=b[0];j++){c[i+j-1]+=a[i]*b[j];}}c[0]=a[0]+b[0]-1;for(int i=1;i<=c[0];i++){c[i+1]+=c[i]/10;c[i]%=10;}if(c[c[0]+1]>0)c[0]++;
}int main()
{freopen("cruel1.in","r",stdin);freopen("cruel1.out","w",stdout);scanf("%d%d",&n,&p);c[0]=1;c[1]=n;while(c[c[0]]>=10){c[0]++;c[c[0]]=c[c[0]-1]/10;c[c[0]-1]%=10;}copy(c,a);b[0]=1;b[1]=1;while(p>0){if(p%2!=0){mutil(a,b,c);copy(c,b);}mutil(a,a,c);copy(c,a);p/=2;}int counter=0;for(int i=b[0];i>=1;i--){if(counter==70){printf("n");counter=0;}counter++;printf("%d",b[i]);}fclose(stdin);fclose(stdout);return 0;
}