#include <iostream>
#include <cstdlib>
#include<cstring>
using namespace std;
#define M 100
char sa[1000];
char sb[1000];
typedef struct _Node{
int s[M]; //储存大数
int l; //代表字符串长度
int c; //次幂
}Node,*pNode;
/*src代表待分解数节点,des表示分解后得到的数节点,st表示从src节点数组中取数开始的位置,l表示取数的长度*/
void cp(pNode src,pNode des,int st,int l)
{
int i,j;
for(i=st,j=0;i<st+l;i++,j++)
{
des->s[j] = src->s[i];
}
des->l = l;
des->c =st + src->c; //次幂
}
void add(pNode pa,pNode pb,pNode ans)
{
int i,cc,k,palen,pblen,len;
int ta,tb;
pNode temp;
if((pa->c<pb->c))
{
temp=pa;
pa=pb;
pb=temp;
}
ans->c =pb->c;
cc =0;
palen =pa->l +pa->c;
pblen =pb->l +pb->c;
if(palen>pblen)
len=palen;
else
len=pblen;
k=pa->c -pb->c;
for(i=0;i<len-ans->c;i++) //次幂高的补0 ,大于低的长度后与0进行计算
{
if(i<k)
ta =0; //k为a左侧需要补0的个数
else
ta =pa->s[i-k]; //i=k时,补0结束,从a数组中第0位开始取数字
if(i<pb->l)
tb =pb->s[i]; //从b数组中第0位开始取数字
else
tb=0; //b数字先取完,b右侧补0
if(i>=pa->l+k) //a数字先取完,a右侧补0
ta =0;
ans->s[i] =(ta+tb+cc)%10; //记录两个之和的个位数,十位做进位处理
cc =(ta+tb+cc)/10;
}
if(cc)
ans->s[i++] =cc;
ans->l =i;
}
void mul(pNode pa,pNode pb,pNode ans)
{
int i,cc,w;
int ma=pa->l>>1;
int mb=pb->l>>1; //长度除2
Node ah,al,bh,bl;
Node t1,t2,t3,t4,z;
pNode temp;
if(!ma||!mb)
{
if(!ma)
{
temp =pa;
pa=pb;
pb=temp;
}
ans->c =pa->c+pb->c;
w =pb->s[0];
cc =0;
for(int i=0;i<pa->l;i++)
{
ans->s[i]=(w*pa->s[i]+cc)%10;
cc =(w*pa->s[i]+cc)/10;
}
if(cc)
ans->s[i++]=cc;
ans->l =i;
return ;
}
cp(pa,&ah,ma,pa->l-ma);
cp(pa,&al,0,ma);
cp(pb,&bh,mb,pb->l-mb);
cp(pb,&bl,0,mb);
mul(&ah,&bh,&t1);
mul(&ah,&bl,&t2);
mul(&al,&bh,&t3);
mul(&al,&bl,&t4);
add(&t3,&t4,ans);
add(&t2,ans,&z);
add(&t1,&z,ans);
}
int main()
{
Node ans,a,b;
cout<<"输入大整数 a"<<endl;
cin>>sa;
cout<<"输入大整数 b"<<endl;
cin>>sb;
a.l=strlen(sa);
b.l=strlen(sb);
int z=0,i;
for(i=a.l-1;i>=0;i--)
{
a.s[z++]=sa[i]-'0';
}
a.c=0;
z=0;
for(i=b.l-1;i>=0;i--)
b.s[z++]=sb[i]-'0';
b.c=0;
mul(&a,&b,&ans);
cout<<"最终的结果为:"<<endl;
for(i=ans.l-1;i>=0;i--)
cout<<ans.s[i];
cout<<endl;
return 0;
}