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.
Sample Input 1 2 1000 2
Sample Output 2 2000
这是一道FFT的入门模板题
#include<stdio.h> #include<cstring> #include<cmath> #include<complex> #include<algorithm> using namespace std; typedef complex<double> complex_t; const double PI = acos(-1.0); const int MAXN = 1 << 18; complex_t A[MAXN], B[MAXN]; char str_1[MAXN], str_2[MAXN]; int res[MAXN], len, len_1, len_2; void Init() { len_1 = strlen(str_1), len_2 = strlen(str_2); int ml = max(len_1, len_2); for(len = 1; len < (ml << 1); len <<= 1); for(int i = 0; i < len_1; ++i) { A[i] = complex_t(str_1[len_1 - i - 1] - '0', 0); } for(int i = 0; i < len_2; ++i) { B[i] = complex_t(str_2[len_2 - i - 1] - '0', 0); } for(int i = len_1; i < len; ++i) { A[i] = complex_t(0, 0); } for(int i = len_2; i < len; ++i) { B[i] = complex_t(0, 0); } } void Rader(complex_t y[]) { for(int i = 1, j = len >> 1, k; i < len - 1; ++ i) { if(i < j) swap(y[i], y[j]); k = len >> 1; while(j >= k) { j -= k; k >>= 1; } if(j < k) j += k; } } void FFT(complex_t y[], int op) { Rader(y); for(int h = 2; h <= len; h <<= 1) { complex_t WN(cos(op * 2.0 * PI / h), sin(op * 2.0 * PI / h)); for(int i = 0; i < len; i += h) { complex_t W(1.0, 0); for(int j = i; j < i + h / 2; ++j) { complex_t u = y[j]; complex_t t = W * y[j + h / 2]; y[j] = u + t; y[j + h / 2] = u - t; W = W * WN; } } } if(op == -1) { for(int i = 0; i < len; ++i) { y[i] = complex_t(y[i].real() / len, y[i].imag() / len); } } } void Output() { int pos = len - 1; while(pos && res[pos] == 0) --pos; while(~pos) putchar(res[pos--] + '0'); putchar('\n'); } void Mul(complex_t x[], complex_t y[]) { for(int i = 0; i < len; ++i) { x[i] = x[i] * y[i]; } } void Slove() { FFT(A, 1); FFT(B, 1); Mul(A, B); FFT(A, -1); res[0] = 0; for(int i = 0; i < len; ++i) { res[i] += (int)(A[i].real() + 0.5); res[i + 1] = res[i] / 10; res[i] %= 10; } Output(); } int main() { while(scanf("%s%s", str_1, str_2) != EOF) { Init(); Slove(); } return 0; }