題目

思路

高精度的問題統(tǒng)一的解決思路是用一個數(shù)組去存大整數(shù)的每一位數(shù),運(yùn)算轉(zhuǎn)化為對數(shù)組的操作.

可以從個位開始存(逆序),也可以從最高位開始存(順序),以處理方便為主要考慮因素.

同時可以將大整數(shù)定義為一個結(jié)構(gòu)體,包含位數(shù),數(shù)組和符號(如有必要).

另外,為了能夠進(jìn)行代碼復(fù)用,通常采用函數(shù)封裝的方式.

以本題為例,步驟如下:

1.將a轉(zhuǎn)化為大整數(shù);

2.將a不斷自乘;

其中大整數(shù)乘法的步驟又分為:

1.遍歷兩個大整數(shù),每位的數(shù)字依次進(jìn)行普通乘法加到對應(yīng)的位上;

2.進(jìn)位.

代碼

代碼一:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define?N?95

typedef?struct{int?cnt,v[N];}BIGINT;

BIGINT?carry(BIGINT?S,int?bin)???//進(jìn)位?bin表示進(jìn)制?binary
{
????int?flag=0;
????for(int?i=0;i<S.cnt;i++)
????{
????????int?temp=S.v[i]+flag;
????????S.v[i]=temp%bin;
????????flag=temp/bin;
????}
????return?S;
}

BIGINT?int2BIG(int?x,int?bin)??//int?轉(zhuǎn)換(to)成BIGINT?
{
????BIGINT?R={0,{0}};
????do
????{
????????R.v[R.cnt++]=x%bin;
????????x/=bin;
????}while(x>0);
????return?R;
}

BIGINT?mul(BIGINT?S,?BIGINT?T)?????//兩個大整數(shù)相乘
{
????BIGINT?R={S.cnt+T.cnt,{0}};??//位數(shù)最多為兩者相加
????for(int?i=0;i<T.cnt;i++)
????{
????????for?(int?j=0;j<S.cnt;j++)
????????{
????????????R.v[i+j]+=S.v[j]*T.v[i];???//依此進(jìn)行普通乘法
????????}
????}
????R=carry(R,10);
????if(R.v[S.cnt+T.cnt-1]==0)?
????{
????????R.cnt--;?//最高位0不統(tǒng)計(jì)在一個大整數(shù)的位數(shù)中
????}
????return?R;
}

BIGINT?pow(BIGINT?a,?int?n)??//計(jì)算?a的n次方
{
????BIGINT?r=int2BIG(1,10);
????for(int?i=0;i<n;i++)
????{
????????r=mul(r,a);
????}
????return?r;
}

int?main()
{
????int?T;
????scanf("%d",&T);
????for(int?t=0;t<T;t++)
????{
????????int?a,n;
????????scanf("%d%d",&a,&n);
????????printf("case?#%d:\n",t);
????????BIGINT?ans=pow(int2BIG(a,10),n);
????????for(int?i=ans.cnt-1;i>=0;i--)
????????{
????????????printf("%d",ans.v[i]);
????????}
????????printf("\n");
????}
}


代碼二(優(yōu)化):

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define?N?95

typedef?struct{int?cnt,v[N];}BIGINT;

BIGINT?carry(BIGINT?S,int?bin)???//進(jìn)位?bin表示進(jìn)制?binary
{
????int?flag=0;
????for(int?i=0;i<S.cnt;i++)
????{
????????int?temp=S.v[i]+flag;
????????S.v[i]=temp%bin;
????????flag=temp/bin;
????}
????return?S;
}

BIGINT?int2BIG(int?x,int?bin)??//int?轉(zhuǎn)換成BIGINT?
{
????BIGINT?R={0,{0}};
????do
????{
????????R.v[R.cnt++]=x%bin;
????????x/=bin;
????}while(x>0);
????return?R;
}

BIGINT?mul(BIGINT?S,?BIGINT?T)?????//兩個大整數(shù)相乘
{
????BIGINT?R={S.cnt+T.cnt,{0}};??//位數(shù)最多為兩者相加
????for(int?i=0;i<T.cnt;i++)
????{
????????for?(int?j=0;j<S.cnt;j++)
????????{
????????????R.v[i+j]+=S.v[j]*T.v[i];???//依此進(jìn)行普通乘法
????????}
????}
????R=carry(R,10);
????if(R.v[S.cnt+T.cnt-1]==0)?
????{
????????R.cnt--;?//最高位0不統(tǒng)計(jì)在一個大整數(shù)的位數(shù)中
????}
????return?R;
}

BIGINT?pow(BIGINT?a,?int?n)??//計(jì)算?a的n次方
{
????BIGINT?r;
????if(n==0)
????{
????????return?int2BIG(1,10);???
????}
????else?if(n==1)
????{
????????return?a;???
????}
????r=pow(a,?n/2);
????r=mul(r,r);
????if(n%2!=0)??//非偶數(shù)?需要多乘一個a?
????{
????????r=mul(r,?a);
????}
????return?r;
}

int?main()
{
????int?T;
????scanf("%d",&T);
????for(int?t=0;t<T;t++)
????{
????????int?a,n;
????????scanf("%d%d",&a,&n);
????????printf("case?#%d:\n",t);
????????BIGINT?ans=pow(int2BIG(a,10),n);
????????for(int?i=ans.cnt-1;i>=0;i--)
????????{
????????????printf("%d",ans.v[i]);
????????}
????????printf("\n");
????}
}