实现了两个长度为n的大数相乘。

#include <cstdio>
#include <cmath>
#include <complex>
using namespace std;
#define pi acos(-1) typedef complex<double> C;
const int N = ;
char s[N],t[N];
int n,m,l,r[N],c[N];
C a[N],b[N]; void fft(C *a, int f) {
for(int i = ; i < n; i++) if(r[i] > i) swap(a[i], a[r[i]]);
for(int i = ; i < n; i <<= ) {
C wn(cos(pi/i), f*sin(pi/i));
for(int j = ; j < n; j += i<<) {
C w = ;
for(int k = ; k < i; k++, w *= wn) {
C x = a[j+k], y = w*a[j+k+i];
a[j+k] = x+y, a[j+k+i] = x-y;
}
}
}
} int main() {
scanf("%d%s%s", &m, s, t);
for(int i = ; i < m; i++) a[i] = s[m-i-]-'', b[i] = t[m-i-]-'';
for(n = , m <<= ; n < m; n <<= ) l++;
for(int i = ; i < n; i++) r[i] = (r[i>>]>>)|((i&)<<(l-));
fft(a, ), fft(b, );
for(int i = ; i < n; i++) a[i] *= b[i];
fft(a, -);
for(int i = ; i < n; i++) a[i] /= n;
for(int i = ; i < m; i++) c[i] = (int)(a[i].real()+0.1);
for(int i = ; i < m; i++) if(c[i] >= ) {
c[i+] += c[i]/, c[i] %= ;
} else if(!c[i] && i == m-) m--;
for(int i = m-; ~i; i--) printf("%d", c[i]);
return ;
}

最新文章

  1. dateRangePicker时间范围控件
  2. Linux下高cpu解决方案(转载)
  3. html5 Application Cache——加快简历二次访问速度
  4. [js开源组件开发]query组件,获取url参数和form表单json格式
  5. struts2中valueStack,stackContext以及actionContext的关系
  6. SHAREPOINT 工作流审批权限问题
  7. [转]C# List&lt;T&gt;的详细用法
  8. C#通过WinAPI获取内存信息,32位64位可用
  9. POJ 3258
  10. c#中 HttpContext作用(一)【转】
  11. 解密电子书之二:EPD控制芯片
  12. Struts2--Action属性接收参数
  13. LDA
  14. Linux 驱动——Button驱动7(Timer)消抖
  15. VBA果然很强大
  16. [转].NET 性能测试工具 -- 事件跟踪器(ETW)
  17. Flex的一些小实例
  18. springboot mybatis 分页整合
  19. MIT molecular Biology 笔记10 翻译
  20. [原创]WebScarab工具介绍

热门文章

  1. 第十二条:考虑实现Comparable接口
  2. 开始使用HTML5和CSS3验证表单
  3. C#中的函数式编程:递归与纯函数(二)
  4. C# 大数组赋值给小数组,小数组赋值给大数组
  5. js回顾(DOM中标签的CRUD,表格等)
  6. gradle入门(1-1)gradle的概念和使用
  7. 运维-替换kibana徽标
  8. 2018年html5入门到精通教程电子书百度云盘下载共22本
  9. 彻底理解了call()方法,apply()方法和bind()方法
  10. HTML5示例之WebSocket