数学(三) |
难度级别:D; 运行时间限制:1800ms; 运行空间限制:262144KB; 代码长度限制:2000000B |
试题描述
|
给出两个正整数a,b,求a*b。
|
输入
|
输入共两行,每行是一个正整数。
|
输出
|
输出共一行,为他们的乘积。
|
输入示例
|
2
2 |
输出示例
|
4
|
其他说明
|
0<a,b<=10^200000
|
经典问题,用FFT加速大整数乘法。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const double PI=acos(-1.0);
struct FFT {
struct cox {
double r,i;
cox(double _r=0.0,double _i=0.0) {r=_r;i=_i;}
cox operator + (const cox& b) {return cox(r+b.r,i+b.i);}
cox operator - (const cox& b) {return cox(r-b.r,i-b.i);}
cox operator * (const cox& b) {return cox(r*b.r-i*b.i,r*b.i+i*b.r);}
}f[maxn];
int len;
void init(char* A,int L,int Len) {
len=L;rep(i,,Len-) f[i]=cox(A[Len-i-]-'',);
}
void fft(int tp) {
int j=len>>;
rep(i,,len-) {
if(i<j) swap(f[i],f[j]);int k=len>>;
while(j>=k) j-=k,k>>=;j+=k;
}
double lm=-*tp*PI;
for(int i=;i<=len;i<<=) {
cox wn(cos(lm/i),sin(lm/i));
for(int j=;j<len;j+=i) {
cox w(,);
for(int k=j;k<j+(i>>);k++) {
cox u=f[k],v=w*f[k+(i>>)];
f[k]=u+v;f[k+(i>>)]=u-v;w=w*wn;
}
}
}
if(tp<) rep(i,,len-) f[i].r/=len;
}
}a,b;
void mul(char* A,char* B,int L1,int L2,int& L,int* ans) {
L=;while(L<L1<<||L<L2<<) L<<=;
a.init(A,L,L1);b.init(B,L,L2);a.fft();b.fft();
rep(i,,L-) a.f[i]=a.f[i]*b.f[i];
a.fft(-);rep(i,,L-) ans[i]=int(a.f[i].r+0.5);
}
char A[maxn],B[maxn];
int ans[maxn];
int main() {
scanf("%s%s",A,B);
int L1=strlen(A),L2=strlen(B),L;
mul(A,B,L1,L2,L,ans);
rep(i,,L-) {
ans[i+]+=ans[i]/;
ans[i]%=;
}
while(L>&&!ans[L-]) L--;
dwn(i,L-,) putchar(ans[i]+'');
return ;
}