可以过下载数据,但是交上去全 RE。
#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double PI = acos(-1.0);
const int N = 4e6 + 10;
struct complex {
double x, y;
complex(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}
complex operator + (complex b) {return complex(x + b.x, y + b.y);}
complex operator - (complex b) {return complex(x - b.x, y - b.y);}
complex operator * (complex b) {return complex(x * b.x - y * b.y, x * b.y + y * b.x);}
}a[N], b[N];
int num[N], n, m, l, r[N], lim = 1;
void FFT(complex *A, int type) {
for(int i = 0; i < lim; i++)
if(i < r[i]) swap(A[i], A[r[i]]);
for(int mid = 1; mid < lim; mid <<= 1) {
complex Wn(cos(PI / mid), type * sin(PI / mid));
for(int R = mid << 1, j = 0; j < lim; j += R) {
complex w(1, 0);
for(int k = 0; k < mid; k++, w = w * Wn) {
complex x = A[j + k], y = w * A[j + k + mid];
A[j + k] = x + y;
A[j + k + mid] = x - y;
}
}
}
}
inline int read(complex *A, int &len) {
int c = getchar(); len = -1;
for(; !isdigit(c); c = getchar());
for(; isdigit(c); c = getchar())
num[++len] = c - '0';
for(int i = 0; i <= len; i++)
A[i].x = num[len - i];
}
int main() {
read(a, n);
read(b, m);
while(lim <= n + m) lim <<= 1, ++l;
for(int i = 0; i < lim; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
FFT(a, 1);
FFT(b, 1);
for(int i = 0; i <= lim; i++) a[i] = a[i] * b[i];
FFT(a, -1);
memset(num, 0, sizeof(num));
for(int i = n + m; ~i; i--)
num[i] = (int) (a[i].x / lim + 0.5);
for(int i = 0; i <= n + m; i++)
if(num[i] > 9)
num[i + 1] += num[i] / 10,
num[i] %= 10;
for(int i = n + m + (num[n + m + 1] > 0); ~i; i--)
putchar(num[i] + '0');
return 0;
}