SPOJ/VFMUL.cc

   1 #include <bits/stdc++.h>
   2
   3 typedef long long int64;
   4
   5 const int SZ = 21, N = 1 << SZ;
   6 const int64 MOD = 479 * N + 1, g = 3;
   7
   8 int64 w[N];
   9
  10 inline int64 pow(int64 base, int64 exp) {
  11   int64 res = 1;
  12   for (; exp; exp >>= 1) {
  13     if (exp & 1) (res *= base) %= MOD;
  14     (base *= base) %= MOD;
  15   }
  16   return res;
  17 }
  18
  19 #define lg2(x) (31 - __builtin_clz(x))
  20
  21 void DFT(int64 *a, int len, int sw) {
  22   static int64 t[N];
  23   for (int i = 0; i < len; ++i) {
  24     int p = 0;
  25     for (int cnt = lg2(len), num = i; cnt--; num >>= 1) (p <<= 1) |= num & 1;
  26     t[i] = a[p];
  27   }
  28   for (int m = 2; m <= len; m *= 2) {
  29     int gap = m / 2, layer = len / m;
  30     for (int i = 0; i < gap; ++i) {
  31       int64 w = (sw == 1) ? ::w[i * layer] : ::w[len - i * layer];
  32       for (int j = i; j < len; j += m) {
  33         int64 u = t[j], v = t[j + gap];
  34         t[j] = (u + w * v % MOD) % MOD;
  35         t[j + gap] = ((u - w * v % MOD) % MOD + MOD) % MOD;
  36       }
  37     }
  38   }
  39   for (int i = 0; i < len; ++i) a[i] = t[i];
  40 }
  41
  42 inline int RD(int64 *a) {
  43   static char s[N];
  44   scanf(" %s", s);
  45   int len = strlen(s);
  46   std::reverse(s, s + len);
  47   for (int i = 0; i < len; ++i) a[i] = s[i] - '0';
  48   return len;
  49 }
  50
  51 int main() {
  52 #ifndef ONLINE_JUDGE
  53   freopen("in.txt", "r", stdin);
  54 #endif
  55   int tcase;
  56   for (scanf("%d", &tcase); tcase--;) {
  57     static int64 a[N], b[N];
  58     int la = RD(a), lb = RD(b);
  59     int len = 1;
  60     while (len < la || len < lb) len *= 2;
  61     len *= 2;
  62     std::fill(a + la, a + len + 1, 0);
  63     std::fill(b + lb, b + len + 1, 0);
  64     w[0] = 1, w[1] = pow(g, (MOD - 1) / len);
  65     for (int i = 2; i <= len; ++i) w[i] = w[i - 1] * w[1] % MOD;
  66     DFT(a, len, 1);
  67     DFT(b, len, 1);
  68     for (int i = 0; i < len; ++i) (a[i] *= b[i]) %= MOD;
  69     DFT(a, len, -1);
  70     int64 inv = pow(len, MOD - 2);
  71     for (int i = 0; i < len; ++i) (a[i] *= inv) %= MOD;
  72     for (int i = 0; i < len; ++i) {
  73       a[i + 1] += a[i] / 10;
  74       a[i] %= 10;
  75     }
  76     while (len && !a[len]) --len;
  77     for (int i = len; i >= 0; --i) putchar(a[i] + '0');
  78     putchar('\n');
  79   }
  80   return 0;
  81 }