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
| #include <bits/stdc++.h> using namespace std;
const double PI = acos(-1); typedef complex<double> Complex; const int maxn = 3e6 + 10;
Complex a[maxn], b[maxn]; int m, n; int bit = 2, rev[maxn]; int ans[maxn];
void get_rev(){ memset(rev, 0, sizeof(rev)); while(bit <= n + m) bit <<= 1; for(int i = 0; i < bit; ++i) { rev[i] = (rev[i >> 1] >> 1) | (bit >> 1) * (i & 1); } }
void FFT(Complex *a, int op) { for(int i = 0; i < bit; ++i) { if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int mid = 1; mid < bit; mid <<= 1) { Complex wn = Complex(cos(PI / mid), op * sin(PI / mid)); for(int j = 0; j < bit; j += mid<<1) { 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; } } } }
int main() { int T; scanf("%d", &T); while(T--) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); string s1, s2; cin >> s1 >> s2; n = s1.size(), m = s2.size(); for(int i = 0; i < n; ++i) { a[i] = s1[n - i - 1] - '0'; } for(int i = 0; i < m; ++i) { b[i] = s2[m - i - 1] - '0'; } get_rev(); FFT(a, 1); FFT(b, 1); for(int i = 0; i <= bit; ++i) { a[i] *= b[i]; } FFT(a, -1); for(int i = 0; i < n + m; ++i) { ans[i] = (int)(a[i].real() / bit + 0.5); } for(int i = 1; i < n + m; ++i) { ans[i] = ans[i] + ans[i - 1] / 10; ans[i - 1] = ans[i - 1] % 10; } int s = n + m - 1; for(; s >= 0; --s) { if(ans[s]) break; } if(s < 0) printf("0\n"); else { for(int i = s; i >= 0; --i) { printf("%d", ans[i]); } printf("\n"); } } return 0; }
|