算法提高 P1001
时间限制:1.0s 内存限制:256.0MB
当两个比较大的整数相乘时,可能会出现数据溢出的情形。为避免溢出,可以采用字符串的方法来实现两个大数之间的乘法。
具体来说,首先以字符串的形式输入两个整数,每个整数的长度不会超过8位,然后把它们相乘的结果存储在另一个字符串当中
(长度不会超过16位),最后把这个字符串打印出来。
例如,假设用户输入为:62773417和12345678,则输出结果为:774980393241726.
输入:
62773417 12345678
输出:
774980393241726
如果只是为了应付OJ系统的判分直接利用 分治乘法 配合long long int 输出 即可解决
#include "stdio.h"
#include "math.h"
int main()
{
long long int S; //long long int 长度远大于题目要求的16位之内
int n=,i,j,k1,k2,L1,L2,A,B,C,D,m1,m2,m3,p,q;
scanf("%d",&p);
scanf("%d",&q);
if(p>q)
j=p;
else
j=q;
while(j!=)
{
j=j/;
n++;
} //此处计算最长数字的长度
L1=L2=n/;
for(i=,k1=p;i<L1;i++)
{
k1=k1/;
}
A=k1;
for(i=;i<L1;i++)
{
k1=k1*;
}
B=p-k1; for(i=,k2=q;i<L2;i++)
{
k2=k2/;
}
C=k2;
for(i=;i<L2;i++)
{
k2=k2*;
}
D=q-k2; m1=A*C;
m2=(A-B)*(D-C);
m3=B*D;
S=(m1*pow(,n)+(m1+m2+m3)*pow(,n/)+m3);//题目以十进制数为主故采用pow(10,x)同理可换成其他进制
printf("%lld\n",S);
return ;
}
判分结果:
大整数乘法原理简单来说就是把长数字拆分(此处为十进制)
即可得出 X=A*10n/2+B ,Y=C*10n/2+D
再推算得X*Y=AC*10n+[(A-B)(D-C)+AC+BD]*10n/2+BD
蓝桥练习系统的样例数据如下:
No. input output
1. 7563975 985872 7457111161200
2. 74863517 5896712 441448599056104
3. 658942 98541 64932803622
4. 96574832 54789216 5291259330611712
5. 32514689 25478691 828431713992099
6. 123 0 0