```cpp
/*
快速傅里叶变换的代码。
先做纯FFT再输出点值。
FFT
利用分治算法，将len个函数值求出来
LUOGUP1919
*/
#include <cstdio>
#include <iostream>
#include <complex>
#include <cstring>
#include <cmath>
#define F(i,j,n) for(register int i=j;i<=n;++i)
using namespace std;
typedef complex<double> com;
const int N = 150007;
const double PI = acos(-1) , SAML = 1e-14;
char A[N], B[N], C[N];
complex<double> a[2*N], b[2*N], c[2*N];
int ans[2*N];
int lena, lenb, len, loglen;
int pw(int a, int x);
void test(com p[]);
int diandao(int x, int len){
int r=0;
F(i, 0, len-1){
r |= ((x >> i) & 1) << (len - 1 - i) ;
}
return r;
}
void sot(com p[]){ //排序
for(int i=0; i<len; ++i){
int j = diandao(i, loglen);
if(i < j) swap(p[i], p[j]);
}
}
void FFT(com p[], int on/*1为FFT，-1为IFFT*/){
for(int l=2; l<=len; l<<=1){
com wn = com( cos(2* PI/((double)l)), on*sin(2* PI/((double)l) ));
for(int j=0; j<len; j+=l){
com w = com(1, 0);
for(int k=0; k < l/2 ; ++k){
com evn = p[j+k];
com od = w * p[j + k + l/2];
p[j+k] = evn + od;
p[j+k+l/2] = evn - od;
w = w * wn;
}
}
}
}
void chengfa()
{
F(i, 0, len-1)
c[i] = a[i] * b[i];
}
int main()
{
freopen("testdata.in", "r", stdin);
freopen("testdata.out", "w", stdout);
int mamamoma;
cin >> mamamoma;
scanf("%s%s", A, B);
lena = strlen(A);
lenb = strlen(B);
len=1;
while(len < lena*2 || len < lenb*2)
len <<= 1;
while((len >> loglen) > 1)
++loglen;
F(i, 0, lena-1)
a[i] = com(A[lena - i - 1] - '0',0);
F(i, 0, lenb-1)
b[i] = com(B[lenb - i - 1] - '0',0);
F(i, lena, len-1)
a[i] = com(0,0);
F(i, lenb, len-1)
b[i] = com(0,0);
sot(a);sot(b);//cmoplete OK
FFT(a, 1); FFT(b, 1);//complete OK
chengfa();
sot(c);//sot 两次就会回到初始的顺序
FFT(c, -1);
F(i, 0, len-1){
ans[i] = int(c[i].real()/len+0.5);
}
F(i, 0, len-1){
if(ans[i]>=10){
ans[i+1] += ans[i] /10;
ans[i] %= 10;
}
}
len = lena + lenb;
while(ans[len] <= 0 && len > 0) --len;
for(int i=len; i>=0; --i){
printf("%d", ans[i]);
}
printf("\n");
return 0;
}
/*仓库
struct fushu//复数 单词complex
{
double r, i;
fushu(double pr=0.0, double pi=0.0) {r=pr; i=pi;}
fushu operator + (const fushu &b) const { return fushu(r+b.r, i+b.i);}
fushu operator - (const fushu &b) const { return fushu(r-b.r, i-b.i);}
fushu operator * (const fushu &b) const { return fushu(r*b.r-i*b.i,r*b.i+i*b.r);}
};
2
21
25
//*/
int pw(int a, int x)
{
int r = a;
while(--x)
r*=a;
return r;
}
void test(com p[]){
printf("debug{\n");
F(i, 0, len-1)
cout << p[i];
printf("\n}\n");
}
```
by lightmain @ 2019-01-26 21:19:43
emm是freopen没删吧
by 漆原琉华 @ 2019-01-26 21:30:45
@[lightmain](/space/show?uid=61904)
by 漆原琉华 @ 2019-01-26 21:31:57
@[漆原琉华](/space/show?uid=10541)
Oh， HAHAHAHA
谢谢
by lightmain @ 2019-01-27 07:36:44