https://www.luogu.org/problemnew/show/P1303(题目传送门)
看到数据范围, 显然要用高精度算法(乘法).
首先用字符串读下这最多达 10^2000 的数, 并判断符号. 若为负号, 我们只用把它的数值存到数组里就行了; 否则, 就将它所有元素都存到数组里.(注意, 若两数异号, 则需输出一个负号.)
之后就到了高精度乘法的核心: 仍然用竖式的思想, 通过几个例子发现, a[i]与 b[i]的乘积都会被加到用与存储结果的输出 c 中的 c[i+j-1]中. 而对于 c[i+j-1], 我们只需要考虑 a[i]*b[i]的值与它原来的值 (进位与上次关于它的乘法) 就好. 若 c[i+j-1]大于 10, 就让它的下一位 c[i+j]+=c[i+j-1](即进位), 并保留 c[i+j-1]的个位. 如此下来, 就得到了结果 -- 最多为 i+j 位的数, 之后就开始判断 (首位 0) 并输出了.
上代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- int a[2001],b[2001],c[4002];
- char s1[2002],s2[2002];
- int main()
- {
- cin>>s1>>s2;
- bool fu=0;
- int j1=strlen(s1),j2=strlen(s2);
- if(s1[0]=='-')
- {
- --j1;
- fu=!fu;
- }
- if(s2[0]=='-')
- {
- --j2;
- fu=!fu;
- }
- if(fu) cout<<'-';
- for(int i=1;i<=j1;++i)
- a[i]=s1[strlen(s1)-i]-'0';
- for(int i=1;i<=j2;++i)
- b[i]=s2[strlen(s2)-i]-'0';
- for(int i=1;i<=j1;++i)
- {
- for(int j=1;j<=j2;++j)
- {
- c[i+j-1]+=a[i]*b[j];
- if(c[i+j-1]>=10)
- {
- c[i+j]+=c[i+j-1]/10;
- c[i+j-1]%=10;
- }
- }
- }
- int k=j1+j2;
- while(!c[k]&&k>1) k--;
- for(;k>=1;k--)
- cout<<c[k];
- return 0;
- }
几点注意:
1,a 数组和 b 数组倒序存的是输入数的大小, 因此应将 s1,s2 的每一位 -'0'再存入数组(取字符与'0'的相对位置, 即字符代表意义上的数值的大小, 而不是 ASCLL 码的大小)
2,(如果 c 全 0 的话)注意保留 c 最后一位 0 输出.(防止积为 0 但是没输出的情况).
来源: http://www.bubuko.com/infodetail-2974455.html