代码

#include <stdio.h>
#include <string.h>
#include <math.h>
#define N (10000 + 5)
struct complex
{
    double real;
    double imag;
    inline complex operator+(const complex &second)
    {
        complex c;
        c.real = real + second.real;
        c.imag = imag + second.imag;
        return c;
    }
    inline complex operator-(const complex &second)
    {
        complex c;
        c.real = real - second.real;
        c.imag = imag - second.imag;
        return c;
    }
    inline complex operator*(const complex &second)
    {
        complex c;
        c.real = real * second.real - imag * second.imag;
        c.imag = imag * second.real + real * second.imag;
        return c;
    }
    inline complex conj()
    {
        return {real, -imag};
    }
};
const double pi = acos(-1.0);
char a[N]; //读入的第一个整数字符串
char b[N]; //读入的第二个整数字符串
int len1, len2, len;
int len11, len22;
complex A[N / 2];  //原始向量1
complex B[N / 2];  //原始向量2
complex yy[N / 2]; //结果向量
complex y[N / 2];  //位逆序处理过的结果向量
long long x[N / 2];
int cc[N * 2];
char c[N * 2];

int log2(int n)
{ //得到[log2(n)]用于位数的扩充
    if (n == 0)
        return -1;
    if (n == 1)
        return 0;
    if (n % 2)
        return log2((n >> 1) + 1) + 1;
    else
        return log2(n >> 1) + 1;
}
inline int rev(int data, int bitnum)
{ //对整数进行位逆序，用于FFT的高效实现
    int temp = 0;
    for (int i = 0; i < bitnum; ++i)
    {
        temp <<= 1;
        temp |= (data >> i) & 0x01;
    }
    return temp;
}
inline int _getai(int sub)
{
    if (sub >= len11)
        return 0;
    return a[len11 - sub - 1] - '0';
}
inline int _getbi(int sub)
{
    if (sub >= len22)
        return 0;
    return b[len22 - sub - 1] - '0';
}
//压位操作
inline int getai(int sub)
{
    return 10000 * _getai(5 * sub + 4) + 1000 * _getai(5 * sub + 3) + 100 * _getai(5 * sub + 2) + 10 * _getai(5 * sub + 1) + _getai(5 * sub);
}
inline int getbi(int sub)
{
    return 10000 * _getbi(5 * sub + 4) + 1000 * _getbi(5 * sub + 3) + 100 * _getbi(5 * sub + 2) + 10 * _getbi(5 * sub + 1) + _getbi(5 * sub);
}
void fftmutiply()
{ //进行两次FFT和一次逆FFT，得到结果并输出
    int maxl = (len1 > len2) ? len1 : len2;
    int ex = log2(maxl);
    len = 1 << ex;
    //位逆序置换构建初始向量
    for (int i = 0; i < (len << 1); ++i)
    {
        A[rev(i, ex + 1)] = {getai(i), 0};
        B[rev(i, ex + 1)] = {getbi(i), 0};
    }
    //进行两次FFT
    for (int s = 1; s <= ex + 1; ++s)
    {
        int m = 1 << s;
        complex omega_m;
        omega_m.real = cos(2 * pi / m);
        omega_m.imag = sin(2 * pi / m);
        for (int k = 0; k < len << 1; k += m)
        {
            complex omega;
            omega.real = 1;
            omega.imag = 0;
            for (int j = 0; j < m / 2; ++j)
            {
                complex ta = omega * A[k + j + m / 2];
                complex ua = A[k + j];
                A[k + j] = ua + ta;
                A[k + j + m / 2] = ua - ta;
                complex tb = omega * B[k + j + m / 2];
                complex ub = B[k + j];
                B[k + j] = ub + tb;
                B[k + j + m / 2] = ub - tb;
                omega = omega * omega_m;
            }
        }
    }
    //得到结果向量
    for (int i = 0; i < len << 1; ++i)
    {
        yy[i] = A[i] * B[i];
    }
    //对结果向量进行位逆序置换
    for (int i = 0; i < len << 1; ++i)
    {
        y[rev(i, ex + 1)] = yy[i];
    }
    //对结果向量进行逆FFT
    for (int s = 1; s <= ex + 1; ++s)
    {
        int m = 1 << s;
        complex omega_m;
        omega_m.real = cos(2 * pi / m);
        omega_m.imag = -sin(2 * pi / m);
        for (int k = 0; k < (len << 1); k += m)
        {
            complex omega;
            omega.real = 1;
            omega.imag = 0;
            for (int j = 0; j < m / 2; ++j)
            {
                complex t = omega * y[k + j + m / 2];
                complex u = y[k + j];
                y[k + j] = u + t;
                y[k + j + m / 2] = u - t;
                omega = omega * omega_m;
            }
        }
    }
    bool flag = false;
    int pos = 0;
    for (int i = len1 + len2 - 1; i >= 0; --i)
    {
        x[i] = round(y[i].real / (len << 1));
        if (!flag)
        {
            if (x[i] != 0)
            {
                pos = i;
                flag = true;
            }
        }
    }
    //处理后输出结果
    int cnt = 0;
    while (cnt <= pos || x[cnt])
    {
        x[cnt + 1] += x[cnt] / 100000;
        x[cnt] %= 100000;
        ++cnt;
    }
    for (int i = 0; i < cnt; ++i)
    {
        cc[5 * i] = x[i] % 10;
        x[i] /= 10;
        cc[5 * i + 1] = x[i] % 10;
        x[i] /= 10;
        cc[5 * i + 2] = x[i] % 10;
        x[i] /= 10;
        cc[5 * i + 3] = x[i] % 10;
        x[i] /= 10;
        cc[5 * i + 4] = x[i] % 10;
    }
    int poss = 5 * cnt - 1;
    for (int i = poss; i >= 0; --i)
    {
        if (cc[i] != 0)
        {
            poss = i;
            break;
        }
    }
    for (int i = 0; i <= poss; ++i)
    {
        c[poss - i] = '0' + cc[i];
    }
    c[poss + 1] = 0;
}
int main()
{
    setvbuf(stdin, new char[1 << 20], _IOFBF, 1 << 20);
    setvbuf(stdout, new char[1 << 20], _IOFBF, 1 << 20);
    int n;
    //scanf("%d", &n);
    n = 1;
    while (n--)
    {
        //数组清空，准备接受下一组输入
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(yy, 0, sizeof(yy));
        memset(y, 0, sizeof(y));
        memset(x, 0, sizeof(x));
        memset(cc, 0, sizeof(cc));
        memset(c, 0, sizeof(c));
        scanf("%s", &a);
        scanf("%s", &b);
        len1 = strlen(a);
        len2 = strlen(b);
        if ((len1 == 1 && a[0] == '0') || (len2 == 1 && b[0] == '0'))
        {
            printf("0\n");
            continue;
        }
        len11 = len1;
        len22 = len2;
        len1 = len1 / 5 + 1;
        len2 = len2 / 5 + 1;
        fftmutiply();
        printf("%s\n", c);
    }
    return 0;
}

评测结果