再次求助,#5 TLE (压8位)

P1303 A*B Problem

Micro_Seven @ 2019-12-31 17:31:54

#include<bits/stdc++.h>
using namespace std;
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 addition(string a,string b)
{
    __int128 i;
    int 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 mulplication(string a,string b)
{
    string ans="0",strs;
    int itrs,i,j,k;
    if(compare(a,b)=='>')swap(a,b);
    for(i=a.length()-1;i>=0;i--)
    {
        for(j=b.length()-1;(j+1)/8>0;j-=8)
        {
            itrs=0;
            for(k=j;k>=j-7;k--)
            {
                itrs+=(a.at(i)-'0')*(b.at(k)-'0')*pow(10,j-k);
            }
            strs=itos(itrs);
            for(k=0;k<(a.length()-i-1)+(b.length()-j-1);k++)
                strs.append("0");
            ans=addition(ans,strs);
        }
        itrs=0;
        for(k=j;k>=0;k--)
        {
            itrs+=(a.at(i)-'0')*(b.at(k)-'0')*pow(10,j-k);
        }
        strs=itos(itrs);
        for(k=0;k<(a.length()-i-1)+(b.length()-j-1);k++)
            strs.append("0");
        ans=addition(ans,strs);
    }
    return ans;
}
int main()
{
    string a,b;
    cin>>a>>b;
    cout<<mulplication(a,b);
    return 0;
}

by optimize_2 @ 2019-12-31 17:41:43

@Micro_Seven FFT,请


by Micro_Seven @ 2019-12-31 17:46:31

@optmize_2 ?


by panyf @ 2019-12-31 17:48:10

@Micro_Seven 不要再用string类型了!慢死了!


by Black_Porridge @ 2019-12-31 18:01:25

写的太复杂了吧


by Black_Porridge @ 2019-12-31 18:02:12

你不能在循环时求字符串长度啊肯定超时


by eexyz @ 2019-12-31 18:05:41

FFT


|