代码

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
//const int M = 20000;
const int M = 2500000;
const double PI = acos(-1);

int n;
string num1, num2;

//实现虚数类，成员变量为实部和虚部，也需要实现多种运算
class Complex{
public:
    double x;
    double y;

    Complex(double _x = 0, double _y = 0){
        x = _x;
        y = _y;
    }

    Complex operator*(Complex num){
        return Complex(x * num.x - y * num.y, x * num.y + y * num.x);
    }

    Complex operator+(Complex num){
        return Complex(x + num.x, y + num.y);
    }

    Complex operator-(Complex num){
        return Complex(x - num.x, y - num.y);
    }
};


void FFT(Complex* a, int len, int flag){
    int* pos = new int[len];
    for(int i = 0; i < len; i++){
        //num为系数a_i要去的位置，tmp记录当前i剩余的位数对应的值，cnt记录循环执行次数（共执行log2(len)次)
        int num = 0;
        int tmp = i;
        int cnt = 1;
        while(cnt < len){
            num *= 2;
            num += tmp % 2;
            tmp /= 2;
            cnt *= 2;
        }
        pos[i] = num;
    }

    //更新系数的位置
    for(int i = 0; i < len; i++){
        if(i < pos[i])swap(a[i], a[pos[i]]);
    }

    //i为待合并区间的长度
    for(int i = 1; i < len; i *= 2){
        //w_2i为该迭代中的2i次单位根
        Complex w_2i(cos(PI / i), flag * sin(PI / i));

        //j为已经合并了的长度
        for(int j = 0; j < len; j += i * 2){
            Complex w(1, 0);

            //k为两个待合并区间的第一个区间的系数下标
            for(int k = j; k < j + i; k++){
                Complex num1 = a[k];
                Complex num2 = w * a[k + i];
                a[k] = num1 + num2;
                a[k + i] = num1 - num2;
                w = w * w_2i;
            }
        }
    }

    //IFFT需要对系数除以长度
    if(flag == -1){
        for(int i = 0; i < len; i++)a[i].x /= len;
    }
}


void get_product(string num1, string num2){
    //a、b数组存储倒序放置的两个数字
    Complex a[M], b[M];
    //int len1 = strlen(num1);
    //int len2 = strlen(num2);
    int len1 = num1.length();
    int len2 = num2.length();
    int len = max(len1, len2);

    //若两个数字的位数不是2的次幂，需要在高位补0使得长度为2的次幂；arr_len为补0后的长度
    int arr_len = 1;
    while(arr_len < len1 + len2 - 1)arr_len *= 2;

    for(int i = 0; i < arr_len; i++){
        if(i < len1)a[i].x = double(num1[len1 - 1 - i] - '0');
        else a[i].x = 0;
    }
    for(int i = 0; i < arr_len; i++){
        if(i < len2)b[i].x = double(num2[len2 - 1 - i] - '0');
        else b[i].x = 0;
    }

    //对a、b数组进行FFT操作
    FFT(a, arr_len, 1);
    FFT(b, arr_len, 1);

    for(int i = 0; i < arr_len; i++)a[i] = a[i] * b[i];

    //对a数组进行IFFT操作
    FFT(a, arr_len, -1);

    //处理最终得到的系数
    int* ans = new int[len * 2];
    for(int i = 0; i < len1 + len2 - 1; i++){
        ans[i] = (int)(a[i].x + 0.5);
    }
    //处理进位
    for(int i = 0; i < len1 + len2 - 1; i++){
        if(ans[i] >= 10){
            ans[i + 1] += ans[i] / 10;
            ans[i] %= 10;
        }
    }

    //将最终结果打印出来
    string product = "";
    bool flag = false;
    for(int i = len1 + len2 - 1; i >= 0; i--){
        if(!flag && ans[i]){
            flag = true;
        }
        if(flag)product += char(ans[i] + '0');
    }
    if(!flag)cout << "0" << endl;
    else cout << product << endl;
}

int main(){
    //cin >> n;
    //while(n--){
        cin >> num1 >> num2;
        get_product(num1, num2);
    //}
    return 0;
}

评测结果