蓝桥杯算法提高 P1001(大数乘法)

                  算法提高 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 ;
}

判分结果:

蓝桥杯算法提高 P1001(大数乘法)

大整数乘法原理简单来说就是把长数字拆分(此处为十进制)

蓝桥杯算法提高 P1001(大数乘法)

即可得出 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  

上一篇:Redis与KV存储(RocksDB)融合之编码方式


下一篇:[转]前端利器:SASS基础与Compass入门