【Bzoj2179】超大整数乘法

来源和评测点

Bzoj2179
Luogu1919
Caioj1450
Codevs3123

题目

【题目大意】
给出两个正整数A和B,计算A*B的值。保证A和B的位数不超过100000位。
【输入格式】
读入两个用空格隔开的正整数
【输出格式】
输出A*B的值
【输入样例1】
4
9
【输出样例1】
36
【输入样例2】
56
12
【输出样例2】
672
【输入样例3】
99
99
【输出样例3】
9801

分析

快速傅里叶变换教程和题目分类参见:
【OI之路】11更高级数论-4快速傅里叶变换
其他快速傅里叶变换题目参见:Tag-快速傅里叶变换

将10看作x就好了
注意进位

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=210000;
const double PI=acos(-1.0);
//*******************全局定义*******************
struct Cmplex
{
double r,i;
Cmplex(double a=0,double b=0) {r=a,i=b;}
Cmplex operator +(Cmplex a) {return Cmplex(r+a.r,i+a.i);}
Cmplex operator -(Cmplex a) {return Cmplex(r-a.r,i-a.i);}
Cmplex operator *(Cmplex a) {return Cmplex(r*a.r-i*a.i,r*a.i+i*a.r);}
};
//*******************实现*******************
Cmplex omega[MAXN];
void calc_omega(int n,int op)
{
omega[0]=Cmplex(1,0);
omega[1]=Cmplex( cos(PI*2*op/n),sin(PI*2*op/n) );
for(int i=2;i<=n/2-1;i++) omega[i]=omega[i-1]*omega[1];
}
int n;
int R[MAXN];
void FFT(Cmplex *a,int op)
{
for(int i=0;i<=n-1;i++) if(i<R[i]) swap(a[i],a[R[i]]);
for(int L=1;L<n;L<<=1)//合并前长度
{
calc_omega(L*2,op);
for(int st=0;st<=n-1;st+=L*2)
{
for(int i=0;i<=L-1;i++)
{
Cmplex x=a[st+i];
Cmplex y=omega[i]*a[st+i+L];
a[st+i]=x+y;
a[st+i+L]=x-y;
}
}
}
if(op==-1) for(int i=0;i<=n-1;i++) a[i].r/=double(n);
}
//*******************主函数*******************
char s[MAXN];
Cmplex a[MAXN],b[MAXN];
int ans[MAXN];
int main()
{
int ln;scanf("%d",&ln);
scanf("%s",s+1);for(int i=ln;i>=1;i--) a[ln-i].r=s[i]-'0';
scanf("%s",s+1);for(int i=ln;i>=1;i--) b[ln-i].r=s[i]-'0';
int m=(ln-1)+(ln-1)+1;
n=1;int tmp=0;
while(n<m) tmp++,n*=2;
for(int i=1;i<=n-1;i++) R[i]= (R[i>>1]>>1) | ( (i&1)<<(tmp-1) );//debug
//nlogn二进制翻转
FFT(a,1);FFT(b,1);//求值
for(int i=0;i<=n-1;i++) a[i]=a[i]*b[i];//点值乘法
FFT(a,-1);//插值
for(int i=0;i<=m-1;i++)
{
ans[i]+=round(a[i].r);
if(ans[i]>9)
{
ans[i+1]+=ans[i]/10;
ans[i]%=10;
if(i==m-1) m++;
}
}
for(int i=m-1;i>=0;i--) putchar('0'+ans[i]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2017-12/超大整数乘法.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%