数据需要加强

P1303 A*B Problem

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 %%%%%%


|