代码

#include <bits/stdc++.h>

using namespace std;

typedef complex<double> comp;

const double pi = acos(-1);

namespace FFT {
  int n;
  vector<double> cs, sn;
  vector<int> rev;
  inline void init (int len) {
    n = len;
    
    cs.resize(len);
    rev.resize(len);
    sn.resize(len);
    int bit = 0;
    while ((1<<bit) < len) bit++;
    
    for (int i = 0; i < len; i++) {
      int x = i, ans = 0;
      for (int j = 0; j < bit; j++) {
        ans <<= 1;
        ans |= (x&1);
        x >>= 1;
      }
      rev[i] = ans;
      cs[i] = cos(pi * 2 * i / len);
      sn[i] = sin(pi * 2 * i / len);
    }
  }
  inline void FFT(vector<comp>& a, const int inv = 1) {
    for (int i = 0; i < n; i++) if (rev[i] > i) swap(a[i], a[rev[i]]);
    for (int len = 2; len <= n; len += len) {
      int half = len >> 1;
      for (int i = 0; i < n; i += len) {
        for (int j = 0; j < half; j++) {
          int cur = n / len * j;
          comp t = comp(cs[cur], sn[cur] * inv) * a[i + j + half];
          comp u = a[i + j];
          a[i + j + half] = u - t;
          a[i + j] = u + t;
        }
      }
    }
    if (inv == -1) {
      for (int i = 0; i < n; i++) a[i] /= n;
    }
  }
}

const int N_MAX = 4e6 + 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());
}

评测结果