1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
|
#include <cstdio> #include <complex> #include <cstring> #include <cmath>
using namespace std;
typedef complex<double> Comp;
const Comp (0, 1); const int MAX_N = 50000 + 10; #ifndef M_PI #define M_PI 3.14159265358979323846 #endif
Comp tmp[1 << 17]; void DFT(Comp a, int n, int rev) { if (n == 1) return; for (int i = 0; i < n; i++) { tmp[i] = a[i]; } for (int i = 0; i < n; i++) { if (i & 1) a[n / 2 + i / 2] = tmp[i]; else a[i / 2] = tmp[i]; } Comp a0 = a, a1 = a + n / 2; DFT(a0, n / 2, rev); DFT(a1, n / 2, rev); Comp cur(1, 0); double alpha = 2 M_PI / n rev; Comp step = exp(I alpha); for (int k = 0; k < n / 2; k++) { tmp[k] = a0[k] + cur a1[k]; tmp[k + n / 2] = a0[k] - cur a1[k]; cur = step; }
for (int i = 0; i < n; i++) { a[i] = tmp[i]; } }
char A[MAX_N], B[MAX_N]; Comp a[1 << 17] = { }, b[1 << 17] = { }; int res[1 << 17];
int main() { while (scanf("%s %s", A, B) != EOF) { int lA = strlen(A), lB = strlen(B); int n = 1; while (n < lA + lB) n <<= 1; for (int i = 0; i < n; i++) { a[i] = 0; b[i] = 0; } for (int i = 0; i < lA; i++) { a[i] = A[lA - 1 - i] - '0'; } for (int i = 0; i < lB; i++) { b[i] = B[lB - 1 - i] - '0'; } DFT(a, n, 1); DFT(b, n, 1); for (int i = 0; i < n; i++) { a[i] *= b[i]; } DFT(a, n, -1); for (int i = 0; i < n; i++) { a[i] /= n; } memset(res, 0, sizeof(res)); for (int i = 0; i + 1 < n; i++) { res[i] += int(a[i].real() + 0.5); res[i + 1] = res[i] / 10; res[i] %= 10; } int k = n - 1; while (res[k] == 0) k--; if (k < 0) { printf("0"); } else { while (k >= 0) printf("%d", res[k--]); } printf("n"); }
return 0; }
|
近期评论