为什么超时？再悬关

lucy2012 @ 2024-02-21 19:11:16

#include<bits/stdc++.h>                                                  
using namespace std;
int main(){
    string a,b;
    int a1[2005],b1[2005],sum[4005],ac,bc,num;
    cin>>a>>b;
    ac=a.length();
    bc=b.length();
    num=max(bc,ac);
    for(int i=ac-1;i>=0;i++)
        a1[i]=a[ac-i+1]-'0';
    for(int i=bc-1;i>=0;i++)
        b1[i]=b[bc-i+1]-'0';
    for(int i=0;i<=num*2;i++){
        sum[i]=a1[i]*b1[i];
        sum[i+1]=sum[i]/10;
        sum[i]=sum[i]%10;
    }
    while(num--){
        if(sum[num])
            break;
    }
    num++;
    for(int i=num;i>=0;i--){
        cout<<sum[i];
    }
    return 0;
}

by Axolotl_awa @ 2024-02-21 19:16:44

for(int i=ac-1;i>=0;i--)
        a1[i]=a[ac-i+1]-'0';
    for(int i=bc-1;i>=0;i--)
        b1[i]=b[bc-i+1]-'0';

@lucy2012 是i--

by Orz_Fa @ 2024-02-21 19:18:59

@lucy2012 高精乘也不是这么写的啊，哪有O(n)算法

by lucy2012 @ 2024-02-21 19:19:44

@wuboyan714 谢。。。。。。可还是wa

by Orz_Fa @ 2024-02-21 19:20:12

建议看下题解

by lucy2012 @ 2024-02-21 19:20:48

@Orz_Fa 唔，对哦

by Axolotl_awa @ 2024-02-21 19:22:01

@lucy2012 晕，你的代码怎么输出全是44啊，我调一下，一会儿发

by quxiangyu @ 2024-02-21 19:25:29

@lucy2012 可以这么写

#include <bits/stdc++.h>
using namespace std;
int n,m,a[5005],b[5005],c[10005],len1,len2,len3;
char str1[5005],str2[5005];
signed main(){
    scanf("%s",str1+1);
    scanf("%s",str2+1);
    len1=strlen(str1+1);
    for (int i=1;i<=len1;i++){
        a[i]=str1[i]-'0';
    }
    reverse(a+1,a+len1+1);
    len2=strlen(str2+1);
    for (int i=1;i<=len2;i++){
        b[i]=str2[i]-'0';   
    }
    reverse(b+1,b+len2+1);
    //翻转后，a[1],b[1]都是个位数
    //a[2],b[2]都是十位数，对齐 
    //1303
    if ((len1==1&&a[1]==0)||(len2==1&&b[1]==0)){
        puts("0");
        return 0;
    }
    for (int i=1;i<=len1;i++){
        //计算a[i]* b 
        for (int j=1;j<=len2;j++){
            c[i+j-1]+=a[i]*b[j]; //i+j-1是a[i]*b[j]实际的位数 
        } 
    }
    //c[i]储存的是 下面所有乘出来 的结果的加起来的和（但是没有 进位）
    //c数组长度 
    len3=len1+len2-1;
    for (int i=1;i<=len3;i++){
        c[i+1]+=c[i]/10;
        c[i]%=10; 
    }
    if (c[len3+1]>0) len3++;//最后一位可能出现进位 
    for (int i=len3;i>=1;i--) printf("%d",c[i]);

    return 0;
}

能给个关注吗(T_T)

by Axolotl_awa @ 2024-02-21 19:32:08

#include <iostream>
#include <string>
using namespace std;
#define MAX_N 10010

struct BigInt {
    int data[MAX_N];        // 数据
    bool is_negative;       // 是否为负数。true: 是负数; false: 不是负数
    int len;                // 数的长度
};

// 比较两个BigInt的绝对值大小
int abs_compare(BigInt &a, BigInt &b)
{
    /*
    如果a > b，return 1
    如果a == b，return 0
    如果a < b，return -1
    */

    // 如果a的长度大于b的长度
    if (a.len > b.len) return 1;
    // 如果b的长度大于a的长度
    else if (a.len < b.len) return -1;
    else
    {
        // 长度相同，由高至低比较
        for (int i = a.len-1; i >= 0; i--)
        {
            if (a.data[i] > b.data[i]) return 1;
            else if (a.data[i] < b.data[i]) return -1;
        }
        return 0;
    }
}

// 将一个BigInt清空，将这个BigInt设置为零。
void clear(BigInt &a)
{
    a.is_negative = false;
    a.len = 0;
}

// 将两个BigInt相乘
BigInt mul(BigInt &a, BigInt &b)
{
    BigInt res;
    clear(res);

    // 竖式乘法
    // TODO
    int len = a.len + b.len;

    for(int i = 0;i <= a.len;i++)
    {
        for(int j = 0;j <= b.len;j++)
        {
            res.data[i + j] += a.data[i] * b.data[j];
        }
    }
    for(int i = 0;i <= len;i++)
    {
        res.data[i + 1] += res.data[i] / 10;
        res.data[i] %= 10; 
    }
    while (res.data[len - 1] == 0 && len > 1)
        len--;

    res.len = len;
    res.is_negative = a.is_negative ^ b.is_negative;
    return res;
}

// 输出一个BigInt
void output(BigInt &a)
{
    // 是负数，则输出负号
    if (a.is_negative)
        cout << "-";

    // 从后往前输出
    for (int i = a.len - 1; i >= 0; i--)
        cout << a.data[i];
    cout << endl;
}

// 读入一个BigInt
void read_my_bigint(BigInt &a)
{
    string str;
    cin >> str;

    if (str[0] == '-')
    {
        a.is_negative = true;
        str.erase(0, 1);        // 将'-'从字符串中删除
    }
    else
        a.is_negative = false;

    a.len = str.size();

    for (int i = a.len - 1; i >= 0; i--)
        a.data[i] = str[a.len-1-i] - '0';
}

int main()
{
    BigInt a, b;
    // 读入两个BigInt
    read_my_bigint(a);
    read_my_bigint(b);

    // output(a);
    // output(b);
    // 执行乘法操作
    BigInt res = mul(a, b);

    // 相减
    output(res);
    return 0;
}

好像是爆改版，但是能AC

by lucy2012 @ 2024-02-21 19:42:29

@quxiangyu @wuboyan714 。。。。。。刚才写错了，不是你们写的差，是我看不懂。（震撼）

by Axolotl_awa @ 2024-02-21 20:32:59

#include<bits/stdc++.h>                                                  
using namespace std;
int main(){
    string a,b;
    int a1[2005],b1[2005],sum[4005] = {0},ac,bc,num;
    cin>>a>>b;
    ac=a.length();
    bc=b.length();
    num=bc+ac;
    for(int i=ac-1;i>=0;i--)
        a1[i]=a[ac-i-1]-'0';
    for(int i=bc-1;i>=0;i--)
        b1[i]=b[bc-i-1]-'0';
    for(int i = 0;i < ac;i++)
    {
        for(int j = 0;j < bc;j++)
        {
            sum[i + j] += a1[i] * b1[j];
        }
    }
    for(int i = 0;i < num;i++) // 进位
    {
        sum[i + 1] += sum[i] / 10;
        sum[i] %= 10; 
    }
    while (sum[num - 1] == 0 && num > 1)// 除零
        num--;
    for(int i=num - 1;i>=0;i--){
        cout<<sum[i];
    }
    return 0;
}

@lucy2012