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.
题目大意:求A * B。
思路:快速傅里叶变换的模板题,偷的模板……也不知道使用姿势对不对QAQ。
代码(250MS):(Update:2014年11月16日)
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <complex>
using namespace std;
typedef complex<double> Complex;
const double PI = acos(-); void fft_prepare(int maxn, Complex *&e) {
e = new Complex[ * maxn - ];
e += maxn - ;
e[] = ;
for (int i = ; i < maxn; i <<= )
e[i] = Complex(cos( * PI * i / maxn), sin( * PI * i / maxn));
for (int i = ; i < maxn; i++)
if ((i & -i) != i) e[i] = e[i - (i & -i)] * e[i & -i];
for (int i = ; i < maxn; i++) e[-i] = e[maxn - i];
}
/* f = 1: dft; f = -1: idft */
void dft(Complex *a, int N, int f, Complex *e, int maxn) {
int d = maxn / N * f;
Complex x;
for (int n = N, m; m = n / , m >= ; n = m, d *= )
for (int i = ; i < m; i++)
for (int j = i; j < N; j += n)
x = a[j] - a[j + m], a[j] += a[j + m], a[j + m] = x * e[d * i];
for (int i = , j = ; j < N - ; j++) {
for (int k = N / ; k > (i ^= k); k /= );
if (j < i) swap(a[i], a[j]);
}
} const int MAXN = ;
Complex x1[MAXN], x2[MAXN];
char s1[MAXN / ], s2[MAXN / ];
int sum[MAXN]; int main() {
Complex* e = ;
fft_prepare(MAXN, e);
while(scanf("%s%s",s1,s2) != EOF) {
int n1 = strlen(s1);
int n2 = strlen(s2);
int n = ;
while(n < n1 * || n < n2 * ) n <<= ;
for(int i = ; i < n; ++i) {
x1[i] = i < n1 ? s1[n1 - - i] - '' : ;
x2[i] = i < n2 ? s2[n2 - - i] - '' : ;
} dft(x1, n, , e, MAXN);
dft(x2, n, , e, MAXN);
for(int i = ; i < n; ++i) x1[i] = x1[i] * x2[i];
dft(x1, n, -, e, MAXN);
for(int i = ; i < n; ++i) x1[i] /= n; for(int i = ; i < n; ++i) sum[i] = round(x1[i].real());
for(int i = ; i < n; ++i) {
sum[i + ] += sum[i] / ;
sum[i] %= ;
} n = n1 + n2 - ;
while(sum[n] <= && n > ) --n;
for(int i = n; i >= ;i--) printf("%d", sum[i]);
puts("");
}
}