题目链接：bzoj2179 题目大意： 给出两个n位10进制整数x和y，你需要计算x*y。 n<=60000
题解： RT 把一位看成系数直接上FFT。 注意输出前处理进位和前导0去掉什么的。
还不会非递归的。。
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; #define maxn 60010*2 const double pi=acos(-1); char str[maxn];int ans[maxn]; struct Complex { double x,y; Complex() {x=0;y=0;} Complex(double x,double y):x(x),y(y){} friend Complex operator + (Complex x, Complex y) {return Complex(x.x+y.x,x.y+y.y);} friend Complex operator - (Complex x, Complex y) {return Complex(x.x-y.x,x.y-y.y);} friend Complex operator * (Complex x, Complex y) {return Complex(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);} }a[maxn],b[maxn]; void DFT(Complex *c,int ln,int t) { if (ln==1) return; Complex A0[ln>>1],A1[ln>>1]; for (int i=0;i<=ln;i+=2) A1[i>>1]=c[i+1],A0[i>>1]=c[i]; Complex wn(cos(2*pi/ln),t*sin(2*pi/ln)),w(1,0); DFT(A0,ln>>1,t);DFT(A1,ln>>1,t); for (int i=0;i<(ln>>1);i++,w=w*wn) { c[i]=A0[i]+w*A1[i]; c[i+(ln>>1)]=A0[i]-w*A1[i]; } } void FFT(int n) { int i,fn=1;while (fn<=2*n) fn<<=1; DFT(a,fn,1);DFT(b,fn,1); for (i=0;i<=fn;i++) a[i]=a[i]*b[i]; DFT(a,fn,-1); for (i=0;i<=2*n;i++) ans[i]=(int)(a[i].x/fn+0.5); } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int n,i; scanf("%d",&n);n--; scanf("%s",str); for (i=0;i<=n;i++) a[n-i].x=(double)str[i]-'0'; scanf("%s",str); for (i=0;i<=n;i++) b[n-i].x=(double)str[i]-'0'; FFT(n); for (i=0;i<2*n;i++) { ans[i+1]+=ans[i]/10; ans[i]%=10; } int fn=2*n;while (!ans[fn] && fn) fn--; for (i=fn;i>=0;i--) printf("%d",ans[i]); printf("\n"); return 0; }