# hdu1402 FFT 大數乘法

``````#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i  )
const int N = 1e6 10;
int n;
struct Com{
double r,i;
Com(double r,double i):r(r),i(i){}
Com(){}
Com operator   (const Com& o){
return Com(r o.r,i o.i);
}
Com operator - (const Com& o){
return Com(r-o.r,i-o.i);
}
Com operator * (const Com& o){
return Com(r*o.r-i*o.i,r*o.i i*o.r);
}
};
const double pi = acos(-1.0);
int rev(int id,int len){
int ret = 0;
for(int i=0;(1<<i)<len;i  ){
ret<<=1;
if(id&(1<<i)) ret|=1;
}
return ret;
}
void FFT(Com* a,int len,int DFT){
Com* A = new Com[len];
for(int i=0;i<len;i  )
A[rev(i,len)] = a[i];
for(int s=1;(1<<s)<=len;s  ){
int m = (1<<s);
Com wm = Com(cos(DFT*2*pi/m),sin(DFT*2*pi/m));
for(int k=0;k<len;k =m){
Com w = Com(1,0);
for(int j=0;j<(m>>1);j  ){
Com t = w*A[k j (m>>1)];
Com u = A[k j];
A[k j] = u t;
A[k j (m>>1)] = u-t;
w = w*wm;
}
}
}
if(DFT==-1) for(int i=0;i<len;i  ) A[i].r/=len,A[i].i/=len;
for(int i=0;i<len;i  ) a[i] = A[i];
}
char numA[N],numB[N];
Com a[N],b[N];
int ans[N];
int main(){
while(scanf("%s",numA)==1){
int sa = 0;
int lenA = strlen(numA);
while((1<<sa)<lenA) sa  ;
int sb = 0;
scanf("%s",numB);
int lenB = strlen(numB);
while((1<<sb)<lenB) sb  ;
int len = (1<<(max(sa,sb) 1));
for(int i=0;i<len;i  ){
if(i<lenA) a[i] = Com(numA[lenA-1-i]-'0',0);
else a[i] = Com(0,0);
if(i<lenB) b[i] = Com(numB[lenB-1-i]-'0',0);
else b[i] = Com(0,0);
}
FFT(a,len,1);
FFT(b,len,1);
for(int i=0;i<len;i  )
a[i] = a[i]*b[i];
FFT(a,len,-1);
for(int i=0;i<len;i  )
ans[i] = (int)(a[i].r 0.5);
for(int i=0;i<len-1;i  ){
ans[i 1] =ans[i]/10;
ans[i]%=10;
}
int flag = 0;
for(int i=len-1;i>=0;i--){
if(ans[i]) printf("%d",ans[i]),flag=1;
else if(flag || i==0) printf("0");
}
puts("");
}
return 0;
}
``````