代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e6 + 5;

const double Pi = acos(-1);

struct cpl {
  double x, y;

  cpl operator + (const cpl& a) const {return {x + a.x, y + a.y};}
  cpl operator - (const cpl& a) const {return {x - a.x, y - a.y};}
  cpl operator * (const cpl& a) const {return {x * a.x - y * a.y, x * a.y + y * a.x};}
} a[MAXN], b[MAXN];

int r[MAXN];

void FFT(int n, cpl *a, int t) {
  for (int i = 0; i < n; ++i) {
    if (r[i] < i) swap(a[i], a[r[i]]); 
  }
  for (int k = 1; k < n; k <<= 1) {
    cpl G = {cos(Pi / k), t * sin(Pi / k)};
    for (int i = 0, o = k << 1; i < n; i += o) {
      cpl now = {1, 0};
      for (int j = 0; j < k; ++j, now = now * G) {
        cpl x = a[i + j], y = now * a[i + k + j];
        a[i + j] = x + y;
        a[i + k + j] = x - y;
      }
    }
  }
}

int ans[MAXN];

int main() {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  string s1, s2;
  cin >> s1 >> s2;
  int n = s1.size(), m = s2.size();
  for (int i = 0; i < n; ++i) {
    a[i].x = s1[n - i - 1] - '0';
    a[i].y = 0;
  }
  for (int i = 0; i < m; ++i) {
    b[i].x = s2[m - i - 1] - '0';
    b[i].y = 0;
  }
  int nm = 1, len = 0, nn = n + m - 1;
  while (nm < nn) nm <<= 1, ++len;
  for (int i = 0; i < nm; ++i) {
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (len - 1));
  }
  FFT(nm, a, 1);
  FFT(nm, b, 1);
  for (int i = 0; i <= nm; ++i) {
    a[i] = a[i] * b[i];
  }
  FFT(nm, a, -1);
  for (int i = 0; i < nn; ++i) {
    ans[i] = a[i].x / nm + 0.5;
  }
  int lst = 0;
  for (int i = 0; i < nn || ans[i] > 0; ++i) {
    if (ans[i] > 9) {
      ans[i + 1] += ans[i] / 10;
      ans[i] %= 10; 
    }
    lst = i;
  }
  for (int i = lst; i > -1; --i) {
    cout << ans[i];
  }
  return 0;
}

评测结果