算法前置数学知识可以参考：http://blog.csdn.net/u013351484/article/details/48739415 。

例题：HDU 1402 A * B Problem Plus

AC代码：

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <complex>
using namespace std;
typedef complex<double> Cpx;
const double PI=3.14159265358979;
const int MAX_BIT=17;

char A[1<<(MAX_BIT-1)], B[1<<(MAX_BIT-1)];
Cpx a[1<<MAX_BIT], b[1<<MAX_BIT];
int rev[1<<MAX_BIT], ans[1<<MAX_BIT];

void get_rev(int bit){
    for(int i=0;i<(1<<bit);i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}
void fft(Cpx *a, int n, bool dft=false){
    for(int i=0;i<n;i++)
        if(i<rev[i]) swap(a[i], a[rev[i]]);
    for(int i=1;i<n;i<<=1){
        Cpx wn=exp(Cpx(0, (dft?-1:1)*PI/i));
        for(int j=0;j<n;j+=i<<1){
            Cpx wnk(1, 0);
            for(int k=j;k<j+i;k++){
                Cpx x=a[k], y=wnk*a[k+i];
                a[k]=x+y;
                a[k+i]=x-y;
                wnk*=wn;
            }
        }
    }
    if(dft) for(int i=0;i<n;i++) a[i]/=n;
}

int main(){
    while(scanf("%s %s", A, B)!=EOF){
        memset(ans, 0, sizeof(ans));
        for(int i=0;i<(1<<MAX_BIT);i++) a[i]=b[i]=Cpx(0, 0);
        int bit=0, n=1;
        int lenA=(int)strlen(A), lenB=(int)strlen(B);
        while((1<<bit)<lenA+lenB-1) bit++, n<<=1;
        for(int i=0;i<lenA;i++) a[i]=Cpx(A[lenA-1-i]-'0', 0);
        for(int i=0;i<lenB;i++) b[i]=Cpx(B[lenB-1-i]-'0', 0);
        get_rev(bit);
        fft(a, n); fft(b, n);
        for(int i=0;i<n;i++) a[i]*=b[i];
        fft(a, n, 1);
        for(int i=0;i<n;i++){
            ans[i]+=int(a[i].real()+0.5);
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
        bool f=false;
        for(int i=lenA+lenB-1;i>=0;i--){
            if(ans[i]) f=true;
            if(f||ans[i]) printf("%d", ans[i]);
        }
        printf(f?"\n":"0\n");
    }
    return 0;
}