首页 > 代码库 > FFT模板
FFT模板
#include <cstdio>#include <cmath>#include <cstring>using namespace std; const double pi = acos(-1.0);const int maxn = 500005; struct complex{ double r,i; complex(double r = 0.0,double i = 0.0) :r(r),i(i) {} inline complex operator + (const complex &b) const { return complex(r + b.r,i + b.i); } inline complex operator - (const complex &b) const { return complex(r - b.r,i - b.i); } inline complex operator * (const complex &b) const { return complex(r * b.r - i * b.i,r * b.i + i * b.r); } friend inline void swap(complex &a,complex &b) { complex t = a;a = b;b = t; }}; complex a[maxn << 1],b[maxn << 1];int ans[maxn << 1];char szA[maxn],szB[maxn]; inline void fft(complex * y,int n,int on){ for(int mid = n >> 1,i = 1,j = mid;i < n - 1;i ++) { if(i < j) swap(y[i],y[j]); int k = mid; for(;j >= k;k >>= 1) j -= k; j += k; } for(int h = 2;h <= n;h <<= 1) { complex wn(cos(2 * pi / h),sin(on * 2 * pi / h)); for(int j = 0;j < n;j += h) { complex w(1,0); int midh = h >> 1; for(int k = j;k < j + midh;k ++,w = w * wn) { complex u = y[k],t = w * y[k + midh]; y[k] = u + t; y[k + midh] = u - t; } } } if(on == -1) for(int i = 0;i < n;i ++) y[i].r /= n;} int main(){ int lenA,lenB,len; while(~scanf("%s%s",szA,szB)) { lenA = strlen(szA),lenB = strlen(szB); for(len = 1;len < (lenA << 1) || len < (lenB << 1);len <<= 1); for(int i = 0;i < lenA;i ++) a[i].r = szA[lenA - i - 1] - ‘0‘,a[i].i = 0; for(int i = lenA;i < len;i ++) a[i].r = a[i].i = 0; for(int i = 0;i < lenB;i ++) b[i].r = szB[lenB - i - 1] - ‘0‘,b[i].i = 0; for(int i = lenB;i < len;i ++) b[i].r = b[i].i = 0; fft(a,len,1); fft(b,len,1); for(int i = 0;i < len;i ++) a[i] = a[i] * b[i]; fft(a,len,-1); for(int i = 0;i < len;i ++) ans[i] = a[i].r + 0.5; for(int i = 0;i < len;i ++) if(ans[i] > 9) ans[i + 1] += ans[i] / 10,ans[i] %= 10; int p = lenA + lenB - 1; while(!ans[p] && p) p --; while(p >= 0) putchar(ans[p --] + ‘0‘); putchar(‘\n‘); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。