题目

思路

高精度的问题统一的解决思路是用一个数组去存大整数的每一位数,运算转化为对数组的操作.

可以从个位开始存(逆序),也可以从最高位开始存(顺序),以处理方便为主要考虑因素.

同时可以将大整数定义为一个结构体,包含位数,数组和符号(如有必要).

另外,为了能够进行代码复用,通常采用函数封装的方式.

以本题为例,步骤如下:

1.将a转化为大整数;

2.将a不断自乘;

其中大整数乘法的步骤又分为:

1.遍历两个大整数,每位的数字依次进行普通乘法加到对应的位上;

2.进位.

代码

代码一:

#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)   //进位 bin表示进制 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 转换(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)     //两个大整数相乘
{
    BIGINT R={S.cnt+T.cnt,{0}};  //位数最多为两者相加
    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];   //依此进行普通乘法
        }
    }
    R=carry(R,10);
    if(R.v[S.cnt+T.cnt-1]==0) 
    {
        R.cnt--; //最高位0不统计在一个大整数的位数中
    }
    return R;
}

BIGINT pow(BIGINT a, int n)  //计算 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");
    }
}


代码二(优化):

#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)   //进位 bin表示进制 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 转换成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)     //两个大整数相乘
{
    BIGINT R={S.cnt+T.cnt,{0}};  //位数最多为两者相加
    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];   //依此进行普通乘法
        }
    }
    R=carry(R,10);
    if(R.v[S.cnt+T.cnt-1]==0) 
    {
        R.cnt--; //最高位0不统计在一个大整数的位数中
    }
    return R;
}

BIGINT pow(BIGINT a, int n)  //计算 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)  //非偶数 需要多乘一个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");
    }
}