代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
const double PI = acos(-1.0);
struct Complex {
    double real, imag;
    Complex(double a = 0, double b = 0) : real(a), imag(b) {}
    Complex(const Complex &rhs) : real(rhs.real), imag(rhs.imag) {}
    Complex conj() const { return {real, -imag}; }
    Complex &operator=(const Complex &rhs) {
        real = rhs.real, imag = rhs.imag;
        return *this;
    }
    Complex &operator+=(const Complex &rhs) {
        real += rhs.real, imag += rhs.imag;
        return *this;
    }
    Complex &operator-=(const Complex &rhs) {
        real -= rhs.real, imag -= rhs.imag;
        return *this;
    }
    Complex &operator*=(const Complex &rhs) {
        double tmp1 = real * rhs.real - imag * rhs.imag,
               tmp2 = real * rhs.imag + imag * rhs.real;
        real = tmp1, imag = tmp2;
        return *this;
    }
    Complex &operator/=(const Complex &rhs) {
        double tmp1 = (real * rhs.real + imag * rhs.imag) /
                      (rhs.real * rhs.real + rhs.imag * rhs.imag),
               tmp2 = (imag * rhs.real - real * rhs.imag) /
                      (rhs.real * rhs.real + rhs.imag * rhs.imag);
        real = tmp1, imag = tmp2;
        return *this;
    }
    friend Complex operator+(const Complex &lhs, const Complex &rhs) {
        Complex res(lhs);
        return res += rhs;
    }
    friend Complex operator-(const Complex &lhs, const Complex &rhs) {
        Complex res(lhs);
        return res -= rhs;
    }
    friend Complex operator*(const Complex &lhs, const Complex &rhs) {
        Complex res(lhs);
        return res *= rhs;
    }
    friend Complex operator/(const Complex &lhs, const Complex &rhs) {
        Complex res(lhs);
        return res /= rhs;
    }
} a[N];
void srfft(int n, Complex x[]) {
    if (n == 1) return;
    if (n == 2) {
        Complex A = x[0], B = x[1];
        x[0] = A + B, x[1] = A - B;
        return;
    }
    int l = n >> 2;
    Complex *y[3] = {x, x + (l << 1), x + 3 * l};
    srfft(l << 1, y[0]), srfft(l, y[1]), srfft(l, y[2]);
    Complex A, B, C, D, w(cos(PI / (l << 1)), sin(-PI / (l << 1))), o(1, 0);
    for (int i = 0; i < l; ++i) {
        A = y[0][i], B = y[1][i] * o, C = y[2][i] * o * o * o, D = y[0][i + l];
        x[i] = A + B + C;
        x[i + 2 * l] = A - B - C;
        double tmp = -B.imag;
        B.imag = B.real, B.real = tmp;
        tmp = -C.imag;
        C.imag = C.real, C.real = tmp;
        x[i + l] = D - B + C;
        x[i + 3 * l] = D + B - C;
        o *= w;
    }
}
void bitrev(int n, Complex x[]) {
    for (int i = 0, j = 0; i < n; ++i) {
        if (i < j) swap(x[i], x[j]);
        for (int k = n >> 1; (j ^= k) < k; k >>= 1) {
        }
    }
}
void dft(int n, Complex x[]) { bitrev(n, x), srfft(n, x); }
void idft(int n, Complex x[]) {
    reverse(x + 1, x + n), bitrev(n, x), srfft(n, x);
    for (int i = 0; i < n; ++i) x[i] *= 1.0 / n;
}
char t[N << 2];
int main() {
#ifdef LOCAL
    freopen("..\\in", "r", stdin), freopen("..\\out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    const int block = 4; // 压位
    cin >> (t + 1);
    int len1 = strlen(t + 1); // 字符串长度
    for (int i = len1, j = 0; i > 0; i -= block, ++j) {
        for (int k = block - 1; ~k; --k) {
            if (i - k > 0) {
                a[j].real = a[j].real * 10 + t[i - k] - '0';
            }
        }
    }
    cin >> (t + 1);
    int len2 = strlen(t + 1); // 字符串长度
    for (int i = len2, j = 0; i > 0; i -= block, ++j) {
        for (int k = block - 1; ~k; --k) {
            if (i - k > 0) {
                a[j].imag = a[j].imag * 10 + t[i - k] - '0';
            }
        }
    }
    int len = 1;
    while (len < (len1 + len2 - 1) / block + 1) len <<= 1; // 这边是压位后的长度
    dft(len, a);
    for (int i = 0; i < len; ++i) a[i] *= a[i];
    idft(len, a);
    int top = 0; // 将t想象成一个栈，存放答案
    ll tmp = 0;
    for (int i = 0; i < (len1 + len2 - 1) / block || tmp; ++i) {
        tmp += static_cast<ll>(a[i].imag / 2.0 + 0.5);
        ll j = tmp % 10000; // 压多少位这边多少个0
        for (int i = 1; i <= block; ++i) {
            t[top++] = j % 10 + '0';
            j /= 10;
        }
        tmp /= 10000; // 压多少位这边多少个0
    }
    while (top && t[top - 1] == '0') --top; // 去前导0
    if(!top)cout<<'0';
    while(top)cout<<t[--top];
    return 0;
}

评测结果