A * B Problem Plus HDU - 1402 (FFT)
Calculate A * B. 

InputEach line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000. 
OutputFor each case, output A * B in one line. 
Sample Input

1
2
1000
2

Sample Output

2
2000 题意:求A*B,A和B的长度都小于50000
题解:FFT的板子题,但FFT还不会,之后再贴一些想法
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<stack>
#include<map>
#include<cstdlib>
#include<vector>
#include<string>
#include<queue>
using namespace std; #define ll long long
#define llu unsigned long long
#define INF 0x3f3f3f3f
const double PI = acos(-1.0);
const int maxn = 2e5+;
const int mod = 1e9+; struct Complex{
double x,y;
Complex(double _x=0.0,double _y = 0.0){
x = _x;
y = _y;
}
Complex operator -(const Complex &b)const{
return Complex(x-b.x,y-b.y);
}
Complex operator +(const Complex &b)const{
return Complex(x+b.x,y+b.y);
}
Complex operator *(const Complex &b)const{
return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
}
}; void change(Complex y[],int len){
int i,j,k;
for( i=,j=len/;i<len-;i++)
{
if(i<j)
swap(y[i],y[j]);
k=len/;
while(j>=k)
{
j -= k;
k /= ;
}
if(j < k)
j += k;
}
} void fft(Complex y[],int len,int on){
change(y,len);
for(int h=;h<=len;h <<= ){
Complex wn(cos(-on * * PI /h),sin(-on**PI/h));
for(int j=;j<len;j+=h){
Complex w(,);
for(int k=j;k<j+h/;k++){
Complex u = y[k];
Complex t = w*y[k+h/];
y[k] = u+t;
y[k+h/] = u-t;
w = w*wn;
}
}
}
if(on == -)
for(int i=;i<len;i++)
y[i].x/=len;
} Complex x1[maxn],x2[maxn];
char str1[maxn/],str2[maxn/];
int sum[maxn];
int main()
{
while(scanf("%s",str1) != EOF)
{
scanf("%s", str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
int len = ;
while(len < len1* || len < len2*)
len<<=;
for(int i=;i<len1;i++)
x1[i] = Complex(str1[len1--i]-'',);
for(int i=len1;i<len;i++)
x1[i] = Complex(,);
for(int i=;i<len2;i++)
x2[i] = Complex(str2[len2--i]-'',);
for(int i=len2;i<len;i++)
x2[i] = Complex(,);
fft(x1,len,);
fft(x2,len,);
for(int i=;i<len;i++)
x1[i] = x1[i]*x2[i];
fft(x1,len,-);
for(int i=;i<len;i++)
sum[i] = (int)(x1[i].x + 0.5);
for(int i=;i<len;i++){
sum[i+] += sum[i]/;
sum[i] %= ;
}
len = len1+len2-;
while(sum[len] <= && len > )
len--;
for(int i=len;i>=;i--)
printf("%c",sum[i]+'');
printf("\n");
}
}

最新文章

  1. knockoutjs扩展与使用
  2. 用 正则表达式 限定XML simpleType 定义
  3. ionic2 图片上传
  4. 使用System.IO来读取以及修改文本文件
  5. google快捷键
  6. 【英语】Bingo口语笔记(57) - 常见的口语弱读
  7. 类似与fiddler的抓包工具 burp suite free edition
  8. JavaScript提高:005:ASP.NET使用easyUI TABS标签显示问题
  9. cape town
  10. pcie inbound、outbound及EP、RC间的互相訪问
  11. Codekart 框架
  12. 微信浏览器软键盘弹出与页面resize的问题
  13. DVWA中low级的sql注入漏洞的简单复现
  14. jQuery实现动态分割div—通过拖动分隔栏实现上下、左右动态改变左右、上下两个相邻div的大小
  15. Spark资源调度
  16. 【WPF】附加属性
  17. 在 ubuntu 【6.06、6.10】 上安装 oracle 10.2.0.1,并打补丁 10.2.0.5
  18. Fast R-CNN论文理解
  19. Android 一个应用多个桌面图标
  20. 酷!美国国家安全局(NSA)开源了逆向工程工具 Ghidra

热门文章

  1. &lt;linux下extmail服务的搭建&gt;
  2. c# string.format 的简写 $
  3. 【转】sql server数据库操作大全——常用语句/技巧集锦/经典语句
  4. 转载:Maven实战—Dependencies与DependencyManagement的区别
  5. java 基础 01 变量和注释、数据类型
  6. addin修改启动路径
  7. Java开发工具IntelliJ IDEA本地历史记录的使用方法
  8. .gitignore梳理
  9. PHP函数:mysql_fetch_assoc指针重置
  10. Protocol Buffer学习教程之类库应用(四)