题意：
大数相乘
题解：
由于题范围为10^5;大数据模拟复杂度为O(n^2),需要用FFT实现快速乘。
FFT的原理参考了下方博客：
http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#mjx-eqn-IDFT-equation
模板（kuangbin）：
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <string> using namespace std; #define MAXN 200010 const double PI = acos(-1.0); //复数结构体 struct cop_num { double r,i; cop_num(double _r=0.0,double _i=0.0) {//初始化 r=_r;i=_i; } //重载运算符 cop_num operator +(const cop_num &b) { return cop_num(r+b.r,i+b.i); } cop_num operator -(const cop_num &b) { return cop_num(r-b.r,i-b.i); } cop_num operator *(const cop_num &b) { return cop_num(r*b.r-i*b.i,r*b.i+i*b.r); } }; cop_num x1[MAXN],x2[MAXN]; string str1,str2; int sum[MAXN]; //反转变换 void change(cop_num y[],int len) { int i,j,k; for(int i=1,j=len/2;i<len-1;i++) { if(i<j) swap(y[i],y[j]); k=len/2; while(j>=k) { j-=k; k/=2; } if(j<k) j+=k; } } //on=1时DFT,-1时IDFT void fft (cop_num y[],int len,int on) { change(y,len); for(int h=2;h<=len;h<<=1) { //wn打表 cop_num wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); for(int j=0;j< len;j+=h) { cop_num w(1,0); for(int k=j;k< j+h/2;k++) { cop_num u=y[k]; cop_num t=w*y[k+h/2]; y[k] = u+t; y[k+h/2] = u-t; w = w*wn; } } } if(on==-1) for(int i=0;i< len;i++) y[i].r/=len; } int main() { while(cin>>str1>>str2) { int len1=str1.length(); int len2=str2.length(); int len=1; while(len <len1*2|| len< len2*2) len<<=1; for(int i=0;i<len1;i++) x1[i]=cop_num(str1[len1-1-i]-'0',0); //长度为2^K，原长度不足则补0 for(int i=len1;i<len;i++) x1[i]=cop_num(0,0); for(int i=0;i<len2;i++) x2[i]=cop_num(str2[len2-1-i]-'0',0); for(int i=len2;i<len;i++) x2[i]=cop_num(0,0); //DFT fft(x1,len,1); fft(x2,len,1); for(int i=0;i<len;i++) x1[i]=x1[i]*x2[i]; fft(x1,len,-1); for(int i=0;i<len;i++) sum[i]=(int) (x1[i].r+0.5); for(int i=0;i<len;i++) { sum[i+1]+=sum[i]/10; sum[i]%=10; } //去前导0 len =len1+len2-1; while(sum[len]<=0&&len > 0) len--; for(int i=len;i>=0;i--) printf("%d",sum[i]); cout<<endl; } return 0; }