Problem Description
Calculate A * B.
 
Input
Each line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000.

 
Output
For each case, output A * B in one line.
 
题目大意:求A * B。
思路:快速傅里叶变换的模板题,偷的模板……也不知道使用姿势对不对QAQ。
 

代码(250MS):(Update:2014年11月16日)

 #include <cmath>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <complex>
using namespace std;
typedef complex<double> Complex;
const double PI = acos(-); void fft_prepare(int maxn, Complex *&e) {
e = new Complex[ * maxn - ];
e += maxn - ;
e[] = ;
for (int i = ; i < maxn; i <<= )
e[i] = Complex(cos( * PI * i / maxn), sin( * PI * i / maxn));
for (int i = ; i < maxn; i++)
if ((i & -i) != i) e[i] = e[i - (i & -i)] * e[i & -i];
for (int i = ; i < maxn; i++) e[-i] = e[maxn - i];
}
/* f = 1: dft; f = -1: idft */
void dft(Complex *a, int N, int f, Complex *e, int maxn) {
int d = maxn / N * f;
Complex x;
for (int n = N, m; m = n / , m >= ; n = m, d *= )
for (int i = ; i < m; i++)
for (int j = i; j < N; j += n)
x = a[j] - a[j + m], a[j] += a[j + m], a[j + m] = x * e[d * i];
for (int i = , j = ; j < N - ; j++) {
for (int k = N / ; k > (i ^= k); k /= );
if (j < i) swap(a[i], a[j]);
}
} const int MAXN = ;
Complex x1[MAXN], x2[MAXN];
char s1[MAXN / ], s2[MAXN / ];
int sum[MAXN]; int main() {
Complex* e = ;
fft_prepare(MAXN, e);
while(scanf("%s%s",s1,s2) != EOF) {
int n1 = strlen(s1);
int n2 = strlen(s2);
int n = ;
while(n < n1 * || n < n2 * ) n <<= ;
for(int i = ; i < n; ++i) {
x1[i] = i < n1 ? s1[n1 - - i] - '' : ;
x2[i] = i < n2 ? s2[n2 - - i] - '' : ;
} dft(x1, n, , e, MAXN);
dft(x2, n, , e, MAXN);
for(int i = ; i < n; ++i) x1[i] = x1[i] * x2[i];
dft(x1, n, -, e, MAXN);
for(int i = ; i < n; ++i) x1[i] /= n; for(int i = ; i < n; ++i) sum[i] = round(x1[i].real());
for(int i = ; i < n; ++i) {
sum[i + ] += sum[i] / ;
sum[i] %= ;
} n = n1 + n2 - ;
while(sum[n] <= && n > ) --n;
for(int i = n; i >= ;i--) printf("%d", sum[i]);
puts("");
}
}

最新文章

  1. LeetCode 094 Binary Tree Inorder Traversal
  2. CMD打包文件,解压文件
  3. 链表的C++实现——创建-插入-删除-输出-清空
  4. jQuery 判断页面元素是否存在
  5. sequenza细胞纯度计算
  6. 【转】eclipse 安装插件
  7. (转)PK系列之六:该不该读中文翻译的专业书
  8. JavaScript ECAMScript5 新特性——get/set访问器
  9. vlc_input buffer管理 &amp; 时钟同步(转)
  10. .net后台 Silverlight 页面 动态设置 ASPX 页面 控件的Margin值(位置设置)
  11. Office——检索 COM 类工厂中 CLSID 为 {000209FF-0000-0000-C000-000000000046} 的组件时失败
  12. 微信小程序实现简易留言板
  13. 支持ipV6和ipV4的客户端编程
  14. pythn print格式化输出---------&quot;%s 和 % d&quot; 都是什么意思?
  15. 激活miniconda2环境,出现activate命令不存在的解决方案(activate: No such file or directory)
  16. [Bayes] prod: M-H: Independence Sampler for Posterior Sampling
  17. 安装node.msi 格式的文件失败
  18. 事务的ACID性质
  19. kettle学习笔记(三)——kettle资源库、运行方式与日志
  20. 解决WIN32窗口不响应WM_LBUTTONDBLCLK消息

热门文章

  1. ajxa分页+多条件查询
  2. JSON数据转换为字典型
  3. 【转】 class 和 struct 区别
  4. 【Android测试】【第二节】性能——CPU时间片
  5. angularJS自定义指令间的“沟通”
  6. Magento SSH 下载安装
  7. Android开发笔记:eclipse导入java项目
  8. oracle 条件语句的写法
  9. 获取dom元素的宽度和高度
  10. 分享一个使用APICloud云数据库已上线的商城APP