Description
给出两个n位10进制整数x和y,你需要计算x*y。
Input
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。
Output
输出一行,即x*y的结果。
Sample Input
1 3 4
Sample Output
12 数据范围: n<=60000
HINT
Source
FFT
FFT真是精妙,我选择背代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define pi acos(-1) 8 using namespace std; 9 const int mxn=(1<<17)+7;10 typedef complex cd;11 char sa[mxn],sb[mxn];12 cd a[mxn],b[mxn];13 int rev[mxn],c[mxn];14 int n,l=0;15 double FFT(cd* a,int flag){16 int i,j;17 for(i=0;i >1]>>1)|((i&1)<<(l-1));44 }45 FFT(a,1);FFT(b,1);//系数表达式转为点阵表达式 46 multi();47 FFT(a,-1);//点阵表达式转为系数表达式48 for(i=0;i =10){c[i+1]+=c[i]/10;c[i]%=10;}51 else if(!c[i] && i==m-1)m--;52 for(i=m-1;i>=0;i--)printf("%d",c[i]);53 return 0;54 }