[알고리즘] 백준 13277 - 큰 수 곱셈

#include <iostream>
#include <vector>
#include <cmath>
#include <complex>
#include <algorithm>
using namespace std;

const double PI = acos(-1);
typedef complex<double> cpx;

void FFT(vector<cpx> &f, cpx w){
    int n = f.size();
    if(n == 1) return;


    vector<cpx> even(n / 2), odd(n / 2);
    for(int i=0; i<n; i++){
        (i % 2 ? odd : even)[i / 2] = f[i];
    }

    FFT(even, w * w);
    FFT(odd, w * w);

    cpx wp(1, 0);
    for(int i=0; i<n/2; i++){
        f[i] = even[i] + wp * odd[i];
        f[i + n/2] = even[i] - wp * odd[i];
        wp *= w;
    }

    return;
}

vector<cpx> multiply(vector<cpx> a, vector<cpx> b){
    int n = 1;

    while(n < a.size() + 1 || n < b.size() + 1){
        n *= 2;
    }
    n *= 2;

    a.resize(n);
    b.resize(n);
    vector<cpx> c(n);

    cpx w(cos(2 * PI / n), sin(2 * PI / n));

    FFT(a, w);
    FFT(b, w);

    for(int i=0; i<n; i++){
        c[i] = a[i] * b[i];
    }

    FFT(c, cpx(1, 0) / w);
    for(int i=0; i<n; i++){
        c[i] /= cpx(n, 0);
        c[i] = cpx(round(c[i].real()), round(c[i].imag()));
    }

    return c;
}

int main(){
    string A, B;
    cin >> A >> B;

    vector<cpx> a, b, c;
    for(int i=0; i<A.size(); i++){
        a.push_back(cpx(A[i] - '0'));
    }
    for(int i=0; i<B.size(); i++){
        b.push_back(cpx(B[i] - '0'));
    }

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    c = multiply(a, b);

    int sz = c.size();
    int up = 0;
    vector<int> Ans;

    for(int i=0; i<sz; i++){
        int n = (int)round(c[i].real()) + up;

        up = n / 10;
        Ans.push_back(n % 10);
    }

    while(up > 0){
        Ans.push_back(up % 10);
        up /= 10;
    }

    int i = Ans.size() - 1;
    while(i >= 0){
        if(Ans[i] != 0){
            break;
        }
        i--;
    }

    if(i < 0){
        cout << "0\n";
    }
    else{
        while(i >= 0){
            cout << Ans[i];
            i--;
        }
        cout << "\n";
    }

    return 0;
}