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