A*B问题
问题描述
计算最多20010位十进制正整数A和B的乘积A*B。
输入样例
1259 8
输出样例
10072
问题分析
由于本题要计算最多20010位十进制正整数A和B的乘积A*B，使用常规的计算方法显然不可取。正确的解法是使用高精度计算。由于小学期的时候写过一道题是“Calc++”，那道题涉及到高精度加法、减法、乘法，所以偷了个懒，直接把那个程序的乘法部分截取出来，压位都懒得改了，改了改输入输出就直接交了。 有关高精度加法减法乘法的思路（即Calc++那道题怎么破），之后会写一篇博客来探讨。还有这个压位貌似写得有点蠢……
AC代码
#include <stdio.h>
#include <string.h>
#include <math.h>
char a
[100005],b
[100005];
long long a1
[100005],b1
[100005],c1
[200005];
int main()
{
scanf
("%s %s",a
,b
);
long long la
=strlen(a
),lb
=strlen(b
);
memset
(a1
,0,sizeof(a1
));
memset
(b1
,0,sizeof(b1
));
memset
(c1
,0,sizeof(c1
));
for (long long i
=0;i
<la
;i
+=6)
{
if (la
-1-i
>=0) a1
[i
/6]+=a
[la
-1-i
]-48;
if (la
-2-i
>=0) a1
[i
/6]+=(a
[la
-2-i
]-48)*10;
if (la
-3-i
>=0) a1
[i
/6]+=(a
[la
-3-i
]-48)*100;
if (la
-4-i
>=0) a1
[i
/6]+=(a
[la
-4-i
]-48)*1000;
if (la
-5-i
>=0) a1
[i
/6]+=(a
[la
-5-i
]-48)*10000;
if (la
-6-i
>=0) a1
[i
/6]+=(a
[la
-6-i
]-48)*100000;
}
for (long long i
=0;i
<lb
;i
+=6)
{
if (lb
-1-i
>=0) b1
[i
/6]+=b
[lb
-1-i
]-48;
if (lb
-2-i
>=0) b1
[i
/6]+=(b
[lb
-2-i
]-48)*10;
if (lb
-3-i
>=0) b1
[i
/6]+=(b
[lb
-3-i
]-48)*100;
if (lb
-4-i
>=0) b1
[i
/6]+=(b
[lb
-4-i
]-48)*1000;
if (lb
-5-i
>=0) b1
[i
/6]+=(b
[lb
-5-i
]-48)*10000;
if (lb
-6-i
>=0) b1
[i
/6]+=(b
[lb
-6-i
]-48)*100000;
}
long long k
=0;
for (long long i
=0;i
<lb
/6+2;i
++)
{
for (long long j
=0;j
<la
/6+2;j
++)
{
c1
[i
+j
]+=a1
[j
]*b1
[i
];
}
}
for (long long i
=0;i
<la
/6+lb
/6+4;i
++)
{
c1
[i
]+=k
;
k
=c1
[i
]/1000000;
c1
[i
]%=1000000;
}
k
=-1;
for (long long i
=la
/6+lb
/6+4;i
>=0;i
--)
{
if (c1
[i
]!=0)
{
k
=i
;
break;
}
}
if (k
!=-1) printf
("%lld",c1
[k
]);
for (long long i
=k
-1;i
>=0;i
--)
{
printf
("%06lld",c1
[i
]);
}
if (k
==-1) printf
("0\n");
else printf
("\n");
return 0;
}
