高精度乘法
cpp
const double PI=acos(-1.0);
struct Complex{
double x,y;
Complex(double x=0,double y=0):x(x),y(y){}
Complex operator +(const Complex &t)const{
return {x+t.x,y+t.y};
}
Complex operator -(const Complex &t)const{
return {x-t.x,y-t.y};
}
Complex operator *(const Complex &t)const{
return {x*t.x-y*t.y,x*t.y+y*t.x};
}
};
int rev[N],bit,tot;
void fft(vector<Complex> &a,int inv){
for(int i=0;i<tot;i++){
if(i<rev[i])swap(a[i],a[rev[i]]);
}
for(int mid=1;mid<tot;mid<<=1){
Complex w1(cos(PI/mid),inv*sin(PI/mid));
for(int i=0;i<tot;i+=mid*2){
Complex wk(1,0);
for(int j=0;j<mid;j++,wk=wk*w1){
auto x=a[i+j],y=wk*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
}
}
vector<int> mul(vector<int> &A,vector<int> &B){
vector<Complex> a,b;
int n=A.size()-1,m=B.size()-1;
for(int i=0;i<=n;i++)a.push_back(A[i]);
for(int i=0;i<=m;i++)b.push_back(B[i]);
while((1<<bit)<n+m+1)bit++;
tot=1<<bit;
while(a.size()<tot)a.push_back(0);
while(b.size()<tot)b.push_back(0);
for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
fft(a,1),fft(b,1);
for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
fft(a,-1);
vector<int> C;
for(int i=0,t=0;i<tot||t;i++){
if(i<tot)t+=(int)(a[i].x/tot+0.5);
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
void solve(){
string s,t;
cin>>s>>t;
vector<int> A,B;
for(int i=s.size()-1;i>=0;i--)A.push_back(s[i]-'0');
for(int i=t.size()-1;i>=0;i--)B.push_back(t[i]-'0');
auto ans=mul(A,B);
for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
}