代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int fMaxn = N << 2; // fMaxn >= 4*maxn (1025 need 4096)
namespace FFT {
    // typedef long double ld;
    const double pi = acos(-1.0);
    struct Complex {
        double r, i;
        Complex(double r = 0, double i = 0):r(r), i(i) {};
        Complex operator + (const Complex & rhs) {
            return Complex(r + rhs.r, i + rhs.i);
        }
        Complex operator - (const Complex & rhs) {
            return Complex(r - rhs.r, i - rhs.i);
        }
        Complex operator * (const Complex &rhs) {
            return Complex(r * rhs.r - i * rhs.i, i * rhs.r + r * rhs.i);
        }
    } va[fMaxn], vb[fMaxn], vc[fMaxn];
    void change(Complex F[], int len) {
        int j = len >> 1;
        for(int i = 1; i < len - 1; ++i) {
            if(i < j) {
                swap(F[i], F[j]);
            }
            int k = len >> 1;
            while(j >= k) {
                j -= k;
                k >>= 1;
            }
            if(j < k) {
                j += k;
            }
        }
    }
    void fft(Complex F[], int len, int t) {
        change(F, len);
        for(int h = 2; h <= len; h <<= 1) {
            Complex wn(cos(-t*2.0*pi/h), sin(-t*2.0*pi/h));
            for(int j = 0; j < len; j += h) {
                Complex E(1, 0);
                for(int k = j; k < j + h/2; ++k) {
                    Complex u = F[k];
                    Complex v = E*F[k + h/2];
                    F[k] = u + v;
                    F[k + h/2] = u - v;
                    E = E*wn;
                }
            }
        }
        if(t == -1) {
            for(int i = 0; i < len; i++) {
                F[i].r /= len;
            }
        }
    }
    template<class T>
    int init(T a[], T b[], int la, int lb) {
        int lc = 1, mi = 2*max(la, lb);
        while(lc < mi) {
            lc <<= 1;
        }
        for(int i = 0; i < la; ++i) {
            va[i] = {(double)a[i], 0.0};
        }
        for(int i = la; i < lc; ++i) {
            va[i] = {0.0, 0.0};
        }
        for(int i = 0; i < lb; ++i) {
            vb[i] = {(double)b[i], 0.0};
        }
        for(int i = lb; i < lc; ++i) {
            vb[i] = {0.0, 0.0};
        }
        return lc;
    }
    template<class T>
    int solve(T a[], T b[], T c[], int la, int lb) { // id: [0, la), [0, lb), [0, lc)
        int lc = init(a, b, la, lb);
        fft(va, lc, 1);
        fft(vb, lc, 1);
        for(int i = 0; i < lc; ++i) {
            vc[i] = va[i]*vb[i];
        }
        fft(vc, lc, -1);
        for(int i = 0; i < lc; ++i) {
            c[i] = vc[i].r; // double
            c[i] = (int)round(vc[i].r); // int
            // c[i] = (ll)round(vc[i].r); // ll
        }
        return lc;
    }
}
int a[N], b[N], c[N << 1];
char s[N];
int main() {
    int n = 1e6, m = 1e6;
    scanf("%s", s);
    for (int i = 0; i < n; i++) a[i] = s[n-i-1] - '0';
    scanf("%s", s);
    for (int i = 0; i < m; i++) b[i] = s[m-i-1] - '0';
    int k = FFT::solve(a, b, c, n, m);
    for (int i = k - 1, lz = 1; ~i; i--) {
        if (lz && c[i] != '\0') lz = 0;
        if (!lz) putchar(c[i] + '0');
    }
}

评测结果