博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
FFT模板
阅读量:4580 次
发布时间:2019-06-09

本文共 1440 字,大约阅读时间需要 4 分钟。

//FFT 大整数乘法#include
#include
#include
#include
using namespace std;const int N = 500005;const double pi = acos(-1.0);char s1[N],s2[N];int len,res[N];struct Complex{ double r,i; Complex(double r=0,double i=0):r(r),i(i) {}; Complex operator+(const Complex &rhs) { return Complex(r + rhs.r,i + rhs.i); } Complex operator-(const Complex &rhs) { return Complex(r - rhs.r,i - rhs.i); } Complex operator*(const Complex &rhs) { return Complex(r*rhs.r - i*rhs.i,i*rhs.r + r*rhs.i); }} va[N],vb[N];void rader(Complex F[],int len) //len = 2^M,reverse F[i] with F[j] j为i二进制反转{ int j = len >> 1; for(int i = 1;i < len - 1;++i) { if(i < j) swap(F[i],F[j]); // reverse int k = len>>1; while(j>=k) { j -= k; k >>= 1; } if(j < k) j += k; }}void FFT(Complex F[],int len,int t){ rader(F,len); for(int h=2;h<=len;h<<=1) { Complex wn(cos(-t*2*pi/h),sin(-t*2*pi/h)); for(int j=0;j
=0;--i) { if(res[i]) { high = i; break; } } for(int i=high;i>=0;--i) putchar('0'+res[i]); puts("");}int main(){ while(scanf("%s %s",s1,s2)==2) { init(s1,s2); gao(); } return 0;}

 

转载于:https://www.cnblogs.com/akrusher/p/5402307.html

你可能感兴趣的文章
gitlab 邮件服务器配置
查看>>
Golang关键字—— if/else
查看>>
PHP&MySQL(三)——数组
查看>>
GPS.NET 和 GeoFramework开源了
查看>>
OFO和摩拜共享单车
查看>>
数据适配 DataAdapter对象
查看>>
有序列表ol和定义列表dl,dt,dd
查看>>
联想小新Air 15 安装黑苹果macOS High Sierra 10.13.6过程
查看>>
公共POI导出Excel方法–java
查看>>
次短路——Dijkstra
查看>>
Enter Query Mode Search Tricks Using Enter_Query Built-in in Oracle Forms
查看>>
广州夜景一
查看>>
FMDataBase 打开sqlite的外键约束功能
查看>>
二分图
查看>>
UVA10559&POJ1390 Blocks 区间DP
查看>>
[bzoj 3289] Mato的文件管理
查看>>
hdu 1853 Cyclic Tour(费用流OR二分图最佳匹配,5级)
查看>>
js 对url进行某个参数的删除,并返回url
查看>>
Windows7装Linux虚拟机
查看>>
SQL 操作结果集 -并集、差集、交集、结果集排序
查看>>