HDU 1402

A * B Problem Plus

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26545    Accepted Submission(s): 6964

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.
 
Sample Input
1
2
1000
2
 
Sample Output
2
2000
 
思路分析 : 两个 5e4 的多项式相乘,显然最朴素的 n^2 的高精度乘法是过不去的 , 这里可以用 fft , 将两个数看成是多项式即可
    有几个坑点 , 0 * 654651 = 0 , 要把首位前面的 0 全去掉
代码示例 :

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+5;
const int maxm = 5e5+5;
char s1[maxn], s2[maxn];
const double pi = acos(-1.0); struct Complex{
double x, y;
Complex (double _x=0, double _y=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);
}
};
Complex x1[maxm], x2[maxm];
void change(Complex y[], int len){
for(int i = 1, j = len/2; i < len-1; i++){
if (i < j) swap(y[i], y[j]);
int k = len/2;
while(j >= k){
j -= k;
k /= 2;
}
if (j < k) j += k;
}
} void fft(Complex y[], int len, int on){
change(y, len);
for(int h = 2; h <= len; h <<= 1){
Complex wn(cos(-on*2*pi/h), sin(-on*2*pi/h));
for(int j = 0; j < len; j += h){
Complex w(1, 0);
for(int k = j; k < j+h/2; k++){
Complex u = y[k];
Complex t = w*y[k+h/2];
y[k] = u+t;
y[k+h/2] = u-t;
w = w*wn;
}
}
}
if (on == -1){
for(int i = 0; i < len; i++)
y[i].x /= len;
}
}
vector<int>ans;
int sum[maxm]; int main () { while(~scanf("%s%s", s1, s2)){
int l1 = strlen(s1);
int l2 = strlen(s2);
memset(x1, 0, sizeof(x1));
memset(x2, 0, sizeof(x2));
int len = 1;
while(len < (l1+l2-1)) len <<= 1; for(int i = 0; i < l1; i++) x1[i] = Complex((double)(s1[i]-'0'), 0);
for(int i = l1; i < len; i++) x1[i] = Complex(0, 0);
for(int i = 0; i < l2; i++) x2[i] = Complex((double)(s2[i]-'0'), 0);
for(int i = l2; i < len; i++) x2[i] = Complex(0, 0);
fft(x1, len, 1); fft(x2, len, 1);
for(int i = 0; i < len; i++) x1[i] = x1[i]*x2[i];
fft(x1, len, -1); ans.clear();
ans.resize(l1+l2-1);
for(int i = l1+l2-2; i >= 0; i--){
ans[i] += (int)(x1[i].x+0.5);
if (i != 0) {
ans[i-1] += ans[i]/10;
ans[i] %= 10;
}
else {
int temp = ans[0]/10;
if(temp != 0){
ans[0] %= 10;
ans.insert(ans.begin(), temp);
}
}
}
int pos = 0;
for(int i = 0; i < l1+l2-1; i++) {
pos = i;
if (ans[i] != 0) break;
}
for(int i = pos; i < ans.size(); i++){
printf("%d", ans[i]);
}
printf("\n");
memset(s1, '\0', sizeof(s1));
memset(s2, '\0', sizeof(s2));
} return 0;
}
/*
4121 46
1321 46
*/

最新文章

  1. 舍弃Nunit拥抱Xunit
  2. GET DIAGNOSTICS Syntax
  3. [CMD]oracle数据库的导出导入
  4. HDU 3695 Computer Virus on Planet Pandora(AC自动机模版题)
  5. U盘安装Win7 64位
  6. STM8S TIM4库函数应用
  7. Codeforces Round #203 - D. Looking for Owls
  8. theano安装
  9. Oracle学习笔记_10_判断是否为日期类型
  10. 如何学习java
  11. Python3字符串替换replace(),translate(),re.sub()
  12. unity 使用方法
  13. python 字符串替换、正则查找替换
  14. eslint 的 env 配置是干嘛使的?
  15. svg(二)---半瓶子晃荡
  16. TLS编程
  17. C#应用jstree实现无限级节点的方法
  18. jwt-auth错误小结
  19. iview中tree的事件运用
  20. centos7系统根目录扩容

热门文章

  1. js将单个反斜杠转化为斜杠的问题
  2. codeforce 382 div2 E —— 树状dp
  3. element 树形控件使用
  4. 2018-2-13-win10-UWP--蜘蛛网效果
  5. ie6 ie7下,Li不能自动换行,出现竖排文字现象(PS:li不固定宽度,所有li同一行显示),在ie8却可以
  6. C#面试题整理2(不带答案)
  7. HDU6579 2019HDU多校训练赛第一场1002 (线性基)
  8. The Preliminary Contest for ICPC Asia Shanghai 2019 C Triple(FFT+暴力)
  9. STVD、IAR两种编译器比较
  10. SSL/TLS 配置