代码

#include <bits/stdc++.h>

using namespace std;
typedef double tp;
typedef complex<tp> comp;

const tp pi = (tp)acosl(-1);

namespace FFT {
  int n;
  int *rev;
  comp *omega;
  inline int get_rev(int x, int bit) {
    int ret = 0;
    for (int i = 0; i < bit; i++) {
      ret <<= 1;
      ret |= x & 1;
      x >>= 1;
    }
    return ret;
  }
  
  inline void init(const int size) {
    n = size;
    rev = (int*)realloc(rev, sizeof(int) * n);
    omega = (comp*)realloc(omega, sizeof(comp) * n);
    int bit = 0;
    while ((1 << bit) < n) bit++;
    for (int i = 0; i < n; i++) {
      rev[i] = get_rev(i, bit);
    }
//    comp wi(cos(pi * 2 / n), sin(pi * 2 / n));
    for (int i = 0; i < n; i++)
      omega[i] = comp(cos(pi * 2 * i / n), sin(pi * 2 * i / n));
  }
  
  
  inline void FFT(vector<comp>& a, const int inv = 1) {
    int bit = 0;
    while((1 << bit) < n) bit++;
    for (int i = 0; i < n; i++) {
      if (rev[i] > i) swap(a[rev[i]], a[i]);
      if (inv == -1) omega[i].imag(-omega[i].imag());
    }
    for (int len = 2; len <= n; len <<= 1) {
      int half = len >> 1;
      for (int i = 0; i < n; i += len) {
        for (int j = 0; j < half; j++) {
          comp t = omega[j * (n / len)] * a[i + j + half];
          comp u = a[i + j];
          a[i + j] = u + t;
          a[i + j + half] = u - t;
        }
      }
    }
    if (inv == -1) {
      for (int i = 0; i < n; i++) {
        a[i] /= n;
        omega[i].imag(-omega[i].imag());
      }
    }
  }
};
const int N_MAX = 2e6 + 10;
vector<comp> a, b;
char buf[N_MAX];
int out[N_MAX << 1];
inline bool solve() {
  if (scanf("%s", buf + 1) == EOF) return 0;
  int len1 = (int) strlen(buf + 1);
  a.resize(len1);

  for (int i = 1; i <= len1; i++) {
    a[i-1] = (buf[len1 - i + 1] - '0');
  }
  scanf("%s", buf + 1);
  int len2 = (int) strlen(buf + 1);
  b.resize(len2);

  for (int i = 1; i <= len2; i++) {
    b[i-1] = (buf[len2 - i + 1] - '0');
  }
  int len = 1;
  while (len < len1 + len2) len <<= 1;
  a.resize(len);
  b.resize(len);
  FFT::init(len);
  FFT::FFT(a);
  FFT::FFT(b);
  for (int i = 0; i < len; i++) {
    a[i] = a[i] * b[i];
  }
  FFT::FFT(a, -1);
  for (int i = 0; i < len; i++) {
    out[i] = a[len - i - 1].real() + 0.5;
  }
  for (int i = len - 1; i >= 0; i--) if (out[i] > 9) {
    out[i-1] += out[i] / 10;
    out[i] %= 10;
  }
  int begin = len;
  for (int i = 0; i < len && len == begin; i++) if (out[i]) begin = i;
  for (int i = begin; i < len; i++) {
    putchar(out[i] + '0');
  }
  if (begin == len) printf("0");
  puts("");
  return 1;
}

int main() {
  //freopen("/Users/Schureed/Downloads/in.txt", "r", stdin);
  //freopen("/Users/Schureed/Downloads/out.txt", "w", stdout);
  while (solve());
}

评测结果