题目大意:给定两个高精度整数,求两个数的乘积

FFT大法好

系统的complex比手写慢了2.5倍 简直吓死人- -

  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #define M 131080
  7. #define PI 3.1415926535897932384626433832795028841971
  8. using namespace std;
  9. namespace PoPoQQQ_Complex{
  10. template<typename T>class Complex{
  11. public:
  12. T real,imaginary;
  13. Complex() {}
  14. Complex(T _,T __=0.0):real(_),imaginary(__) {}
  15. Complex& operator += (const Complex<T> &x) { real+=x.real;imaginary+=x.imaginary;return *this; }
  16. Complex& operator -= (const Complex<T> &x) { real-=x.real;imaginary-=x.imaginary;return *this; }
  17. friend Complex operator + (const Complex<T> &x,const Complex<T> &y) { Complex re=x;re+=y;return re; }
  18. friend Complex operator - (const Complex<T> &x,const Complex<T> &y) { Complex re=x;re-=y;return re; }
  19. friend Complex operator * (const Complex<T> &x,const Complex<T> &y)
  20. { return Complex(x.real*y.real-x.imaginary*y.imaginary,x.real*y.imaginary+x.imaginary*y.real); }
  21. Complex& operator *= (const Complex &x) { return *this=(*this)*x; }
  22. };
  23. }
  24. using namespace PoPoQQQ_Complex;
  25. typedef Complex<double> abcd;
  26. int n;
  27. abcd a[M],b[M],p[M];
  28. char s[M];
  29. void FFT(abcd x[],int n,int type)
  30. {
  31. static abcd temp[M];
  32. int i;
  33. if(n==1) return ;
  34. for(i=0;i<n;i+=2)
  35. temp[i>>1]=x[i],temp[i+n>>1]=x[i+1];
  36. memcpy(x,temp,sizeof(abcd)*n);
  37. abcd *l=x,*r=x+(n>>1);
  38. FFT(l,n>>1,type);FFT(r,n>>1,type);
  39. abcd root(cos(2*type*PI/n),sin(2*type*PI/n) ),w(1);
  40. for(i=0;i<n>>1;i++,w*=root)
  41. temp[i]=l[i]+w*r[i],temp[i+(n>>1)]=l[i]-w*r[i];
  42. memcpy(x,temp,sizeof(abcd)*n);
  43. }
  44. int main()
  45. {
  46. int i,digit;
  47. cin>>n;
  48. scanf("%s",s+1);
  49. for(i=0;i<n;i++)
  50. a[i].real=s[n-i]-'0';
  51. scanf("%s",s+1);
  52. for(i=0;i<n;i++)
  53. b[i].real=s[n-i]-'0';
  54. for(digit=1;digit<n<<1;digit<<=1);
  55. FFT(a,digit,1);FFT(b,digit,1);
  56. for(i=0;i<digit;i++)
  57. p[i]=a[i]*b[i];
  58. FFT(p,digit,-1);
  59. static int stack[M],top;
  60. for(i=0;i<=n-1<<1;i++)
  61. {
  62. ++top;
  63. stack[top]+=int(p[i].real/digit+0.5);
  64. stack[top+1]+=stack[top]/10;
  65. stack[top]%=10;
  66. }
  67. if(stack[top+1]) ++top;
  68. while(top)
  69. putchar(stack[top--]+'0');
  70. puts("");
  71. return 0;
  72. }