求助,#4#5TLE

P1303 A*B Problem

Micro_Seven @ 2019-12-30 12:08:04

#include<bits/stdc++.h>
using namespace std;
string addition(string a,string b)
{
    __int128 i,count=0;
    string ans="";
    if(a.length()<b.length())
    {
        for(i=0;i<a.length()-b.length();i++)a.insert(0,"0");
    }
    else
    {
        for(i=0;i<b.length()-a.length();i++)b.insert(0,"0");
    }
    for(i=0;i<a.length();i++)ans.insert(0,"0");
    for(i=a.length()-1;i>=0;i--)
    {
        if((a.at(i)-'0')+(b.at(i)-'0')+count<=9)
        {
            ans.at(i)+=(a.at(i)-'0')+(b.at(i)-'0')+count;
            count=0;
        }
        else
        {
            ans.at(i)+=(a.at(i)-'0')+(b.at(i)-'0')+count-10;
            count=1;
        }
    }
    if(count==1)ans.insert(0,"1");
    while(ans.at(0)=='0'&&ans.length()>1)ans.replace(0,1,"");
    return ans;
}
string itos(int n)
{
    stringstream newstr;
    newstr<<n;
    return newstr.str();
}
char compare(string a,string b)
{
    if(a.length()>b.length())return '>';
    else if(a.length()<b.length())return '<';
    else
    {
        for(__int128 i=0;i<a.length();i++)
        {
            if(a.at(i)>b.at(i))return '>';
            else if(a.at(i)<b.at(i))return '<';
        }
        return '=';
    }
}
string multiplication(string a,string b)
{
    long long i,j,k;
    string trs="0",ans="0";
    if(compare(a,b)=='<')
    {
        for(i=a.length()-1;i>=0;i--)
        {
            for(j=b.length()-1;j>=0;j--)
            {
                trs=itos((a.at(i)-'0')*(b.at(j)-'0'));
                for(k=0;k<(a.length()-i-1)+(b.length()-j-1);k++)
                    trs.append("0");
                ans=addition(ans,trs);
            }
        }
    }
    else
    {
        for(i=b.length()-1;i>=0;i--)
        {
            for(j=a.length()-1;j>=0;j--)
            {
                trs=itos((b.at(i)-'0')*(a.at(j)-'0'));
                for(k=0;k<(a.length()-j-1)+(b.length()-i-1);k++)
                    trs.append("0");
                ans=addition(ans,trs);
            }
        }
    }
    return ans;
}
int main()
{
    string a,b;
    cin>>a>>b;
    cout<<multiplication(a,b);
    return 0;
}

by Schwarzkopf_Henkal @ 2019-12-30 12:23:16

可能要压位吧


by Schwarzkopf_Henkal @ 2019-12-30 12:23:31

@Micro_Seven


by Micro_Seven @ 2019-12-30 12:24:05

@Schwarzkopf_Henkal ???


by Micro_Seven @ 2019-12-30 12:24:17

@Schwarzkopf_Henkal 啥意思


by Schwarzkopf_Henkal @ 2019-12-30 12:26:42

大概就是你不能按一位一位地把高精度数分成很多的低精度数而是要把高精度数按照4位或者8位(如果你用long long)分成一块进行运算@Micro_Seven


by Schwarzkopf_Henkal @ 2019-12-30 12:27:57

你可以理解成把高精度数换成一万进制的数然后每位用一个int存储


by Schwarzkopf_Henkal @ 2019-12-30 12:29:05

https://www.luogu.com.cn/paste/9l4qj2u7

这是我之前存的一个高精模板,看一下

@Micro_Seven


|