jjsnam @ 2022-03-14 22:33:36
AC代码如下,但这应该是错误的
#include <iostream>
#include <string>
using namespace std;
string ina,inb;
short a[2005],b[2005];
short ans[2005];
void Multiply(short a[],short b[]){
ans[0]=a[0]+b[0];
for (int i=1;i<=a[0];i++){
for (int j=1;j<=b[0];j++){
ans[i+j-1]+=a[i]*b[j];
}
}
for (int i=1;i<=ans[0];i++){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
while (ans[0]>1&&ans[ans[0]]==0) ans[0]--;
}
void print(){
for (int i=ans[0];i>0;i--){
cout << ans[i];
}
cout << endl;
}
int main(){
freopen("/Users/liyumei1973/Desktop/信奥赛/作业/sample.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> ina;
cin >> inb;
a[0]=ina.size(),b[0]=inb.size();
for (int i=a[0],j=0;i>0;i--,j++){
a[i]=ina[j]-'0';
}
for (int i=b[0],j=0;i>0;i--,j++){
b[i]=inb[j]-'0';
}
Multiply(a,b);
print();
return 0;
}
问题在于ans数组的大小。 如果按照题目的数据范围,a和b都是2000位的数字,那么他们相乘可以达到4000位数字,以我ans开的数据范围会RE 数据需要加强
by CuBernie @ 2022-03-14 23:15:37
@jjsnam 2000*2000不应该等于4000000吗?c开到4000000以上更为合理吧
by CuBernie @ 2022-03-14 23:17:57
@jjsnam 我逐个试了一遍,这是我的提交记录
by CuBernie @ 2022-03-14 23:18:36
请忽视3月14号之前的
by jjsnam @ 2022-03-15 08:05:43
@Nice_Minecrafter 但我的ans数组开到2000就没问题。 我把#5的数据下载了,分别输出a,b,ans的长度
1284 1251
2534
可以看到ans是2534,但我的ans是2005位 离谱啊????
by jjsnam @ 2022-03-15 08:17:32
@Nice_Minecrafter 可能是我short的问题???改成int后就需要开到4000才能过了
然后关于您开4000000的数组,(仅以个人看法)其实乘法运算改变的位是i+j-1,不是ij,所以两个2000位数组应该是4000左右。 比如114514114514=13113456196 两个6位数相乘得出了一个11位数,符合最高位等于i+j-1。
至于为什么您开成4000会RE……我还是太弱了我解释不了 但我的4000可以过……
by CuBernie @ 2022-03-15 11:47:27
@jjsnam 啊我知道了,问题出在第39行和第48行的i=al*bl,相当于访问了c[4000000],出现了数组越界……
by CuBernie @ 2022-03-15 11:48:31
我是幂运算鬼才!
by CuBernie @ 2022-03-15 11:49:39
焯
by jjsnam @ 2022-03-15 16:03:36
@Nice_Minecrafter %%%%%%