Boj 22289

22289.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <complex>
#include <cstring>

using namespace std;

typedef complex<double> cpx;

#define C(X) (cpx(X))

const double PI = acos(-1);
void DFT(vector<cpx>& f, cpx w) {
    auto n = f.size();
    if(n == 1) return;
    vector<cpx> odd(n / 2), even(n / 2);
    for(int i = 0; i < n; i++)
        (i % 2 ? odd : even)[i / 2] = f[i];
    DFT(odd, w * w);
    DFT(even, w * w);

    cpx wp = cpx(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;
    }
}

void IDFT(vector<cpx>& f, cpx w) {
    DFT(f, cpx(1, 0) / w);
}

vector<int> mul(vector<cpx>& a, vector<cpx>& b) {
    auto a_size = a.size();
    auto b_size = b.size();
    int n = 1;
    while(n <= a_size || n <= b_size) n <<= 1;
    n <<= 1;

    a.resize(n);
    b.resize(n);

    vector<cpx> c(n);

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

    DFT(a, w);
    DFT(b, w);
    for(int i = 0; i < n; i++)
        c[i] = a[i] * b[i];

    IDFT(c, w);

    vector<int> o(n);
    for(int i = 0; i < n; i++) {
        o[i] = round(c[i].real() / n);
    }
    return o;
}

int main() {
    char* a = (char*)malloc(1000005);
    char* b = (char*)malloc(1000005);
    scanf("%s %s", a, b);
    if(*a == '0' || *b == '0') {
        printf("0");
        return 0;
    }
    int len_a = strlen(a);
    int a_siz = (len_a + 1) / 2;
    auto v1 = vector<cpx>(a_siz);
    if(len_a % 2) {
        v1[0] = *a - '0';
        for (int i = 1; i < a_siz; i++)
            v1[i] = C(10 * (a[i * 2 - 1] - '0') + a[i * 2] - '0');
    }
    else for (int i = 0; i < a_siz; i++)
            v1[i] = C(10 * (a[i * 2] - '0') + a[i * 2 + 1] - '0');

    int len_b = strlen(b);
    int b_siz = (len_b + 1) / 2;
    auto v2 = vector<cpx>(b_siz);
    if(len_b % 2) {
        v2[0] = *b - '0';
        for (int i = 1; i < b_siz; i++)
            v2[i] = C(10 * (b[i * 2 - 1] - '0') + b[i * 2] - '0');
    }
    else for (int i = 0; i < b_siz; i++)
            v2[i] = C(10 * (b[i * 2] - '0') + b[i * 2 + 1] - '0');

    auto v3 = mul(v1, v2);

    int t = 0;
    for(int i = a_siz + b_siz - 2; i >= 0; i--) {
        v3[i] += t;
        if(v3[i] >= 100) {
            t = v3[i] / 100;
            v3[i] %= 100;
        }
        else t = 0;
    }

    if(t) {
        printf("%d", t);
        if(v3[0] < 10)
            printf("0%d", v3[0]);
        else printf("%d", v3[0]);
    }
    else printf("%d", v3[0]);
    for(int i = 1; i < a_siz + b_siz - 1; i++)
        if(v3[i] < 10)
            printf("0%d", v3[i]);
        else printf("%d", v3[i]);
    return 0;
}

https://www.acmicpc.net/problem/22289