此处介绍另一种方法来解决这题，也就是FFT(快速傅里叶变换)
如果是乘法，位数为n和位数为m的相乘，需要n*m次的乘法运算。
FFT在数字信号处理学过，但是第一次用来做这类题目，神奇啊。
乘法其实就是做线性卷积。
用DFT得方法可以求循环卷积，但是当循环卷积长度L≥N+M-1，就可以做线性卷积了。
使用FFT将两个数列转换成傅里叶域，在这的乘积就是时域的卷积。
给几个学习的链接吧：
http://wenku.baidu.com/view/8bfb0bd476a20029bd642d85.html （这主要看那个FFT的流程图）
http://wlsyzx.yzu.edu.cn/kcwz/szxhcl/kechenneirong/jiaoan/jiaoan3.htm 这有DFT的原理。
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define pi acos(-1.0) 10 using namespace std; 11 const int MAX = 200002; 12 //复数结构体 13 struct complex{ 14 double r,i; 15 complex(double R=0,double I=0){ 16 r=R;i=I; 17 } 18 complex operator+(const complex &a){ 19 return complex(r+a.r,i+a.i); 20 } 21 complex operator-(const complex &a){ 22 return complex(r-a.r,i-a.i); 23 } 24 complex operator*(const complex &a){ 25 return complex(r*a.r-i*a.i,r*a.i+i*a.r); 26 } 27 }; 28 /* 29 *进行FFT和IFFT前的反转变换 30 *位置i和i的二进制反转后位置互换，(如001反转后就是100) 31 *len必须去2的幂 32 */ 33 void change(complex x[],int len){ 34 int i,j,k; 35 for(i = 1, j = len/2; i <len-1; i++){ 36 if (i < j) swap(x[i],x[j]); 37 //交换互为小标反转的元素，i<j保证交换一次 38 //i做正常的+1,j做反转类型的+1，始终i和j是反转的 39 k = len/2; 40 while (j >= k){ 41 j -= k; 42 k /= 2; 43 } 44 if (j < k) j += k; 45 } 46 } 47 /* 48 *做FFT 49 *len必须为2^n形式，不足则补0 50 *on=1时是DFT，on=-1时是IDFT 51 */ 52 void fft (complex x[],int len,int on){ 53 change(x,len); 54 for (int i=2;i<=len;i<<=1){ 55 complex wn(cos(-on*2*pi/i),sin(-on*2*pi/i)); 56 for (int j=0;j<len;j+=i){ 57 complex w(1,0); 58 for (int k=j;k<j+i/2;k++){ 59 complex u = x[k]; 60 complex t = w*x[k+i/2]; 61 x[k] = u+t; 62 x[k+i/2] = u-t; 63 w = w*wn; 64 } 65 } 66 } 67 if (on == -1){ 68 for (int i=0;i<len;i++){ 69 x[i].r /= len; 70 } 71 } 72 } 73 complex x1[MAX],x2[MAX]; 74 char str1[MAX/2],str2[MAX/2]; 75 ll num[MAX],sum[MAX]; 76 int main() 77 { 78 int i,j,k,len1,len2,len; 79 while(scanf("%s%s",&str1,&str2)!=EOF){ 80 len1 = strlen(str1); 81 len2 = strlen(str2); 82 len = 1; 83 while (len < 2*len1 || len < 2*len2) len<<=1; 84 for (i=0;i<len1;i++){ 85 x1[i] = complex(str1[len1-1-i]-'0',0); 86 } 87 for (i=len1;i<len;i++){ 88 x1[i] = complex(0,0); 89 } 90 for (i=0;i<len2;i++){ 91 x2[i] = complex(str2[len2-1-i]-'0',0); 92 } 93 for (i=len2;i<len;i++){ 94 x2[i] = complex(0,0); 95 } 96 fft(x1,len,1); 97 fft(x2,len,1); 98 for (i=0;i<len;i++){ 99 x1[i] = x1[i]*x2[i]; 100 } 101 fft(x1,len,-1); 102 for (i=0;i<len;i++){ 103 sum[i] = (int)(x1[i].r+0.5); 104 } 105 for (i=0;i<len;i++){ 106 sum[i+1]+=sum[i]/10; 107 sum[i]%=10; 108 } 109 len = len1+len2-1; 110 while (sum[len]<=0 && len>0) len--; 111 for (i=len;i>=0;i--){ 112 printf("%c",sum[i]+'0'); 113 } 114 printf(" "); 115 } 116 return 0; 117 }