SPOJ/MUL.cc

   1 #include <bits/stdc++.h>
   2
   3 const int N = 1 << 15;
   4 const double eps = 1e-5;
   5
   6 const std::complex<double> I(0.0, 1.0);
   7
   8 #define lg2(x) (31 - __builtin_clz(x))
   9
  10 void DFT(std::complex<double> *a, int n, int sw) {
  11   std::complex<double> tmp[N];
  12   for (int i = 0, cnt = lg2(n); i < n; ++i) {
  13     int p = 0;
  14     for (int tp = i, c = 0; c < cnt; tp >>= 1, ++c) (p <<= 1) |= (tp & 1);
  15     tmp[p] = a[i];
  16   }
  17   for (int m = 2; m <= n; m *= 2) {
  18     int gap = m / 2;
  19     for (int i = 0; i < gap; ++i) {
  20       std::complex<double> w(std::exp(I * (sw * 2 * M_PI * i / m)));
  21       for (int j = i; j < n; j += m) {
  22         std::complex<double> u = tmp[j], v = tmp[j + gap];
  23         tmp[j] = u + w * v;
  24         tmp[j + gap] = u - w * v;
  25       }
  26     }
  27   }
  28   for (int i = 0; i < n; ++i) {
  29     a[i] = tmp[i];
  30     if (sw == -1) a[i] /= n;
  31   }
  32 }
  33
  34 int main() {
  35   int kCase;
  36   for (scanf("%d", &kCase); kCase--;) {
  37     static char s[N];
  38     static std::complex<double> a[N], b[N];
  39     memset(a, 0, sizeof a);
  40     memset(b, 0, sizeof b);
  41     scanf(" %s", s);
  42     int t0 = strlen(s);
  43     std::reverse(s, s + t0);
  44     for (int i = 0; i < t0; ++i) a[i] = s[i] - '0';
  45     scanf(" %s", s);
  46     int t1 = strlen(s);
  47     std::reverse(s, s + t1);
  48     for (int i = 0; i < t1; ++i) b[i] = s[i] - '0';
  49     int len = 1;
  50     while (len < std::max(t0, t1)) len *= 2;
  51     len *= 2;
  52     DFT(a, len, 1);
  53     DFT(b, len, 1);
  54     for (int i = 0; i < len; ++i) a[i] *= b[i];
  55     DFT(a, len, -1);
  56     static int ans[N];
  57     std::fill(ans, ans + len + 1, 0);
  58     for (int i = 0; i < len; ++i) {
  59       ans[i] += (int)(a[i].real() + eps);
  60       ans[i + 1] += ans[i] / 10;
  61       ans[i] %= 10;
  62     }
  63     while (len > 0 && ans[len] == 0) --len;
  64     for (int i = len; i >= 0; --i) putchar(ans[i] + '0');
  65     putchar('\n');
  66   }
  67   return 0;
  68 }