Fast Multiplication using FFT

#include<bits/stdc++.h>
using namespace std;

#define     rep(i,k,n)      for(int i=k;i<n;i++)
#define     PI              acos(-1)
#define     MP(x, y)        make_pair(x, y)
#define     PB(x)           push_back(x)
#define     ALL(p)          p.begin(),p.end()
#define     CLR(p)          memset(p, 0, sizeof(p))
#define     MEM(a, b)       memset(a, (b), sizeof(a))
#define     PII             pair<int, int>
#define     ll              long long int
#define     ull             unsigned long long int

using cd = complex<double>;

void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}

vector<int> multiply(vector<int> const& a, vector<int> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size())
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}


int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s1, s2;
        cin >> s1 >> s2;

        vector<int> a, b;
        for(auto i:s1)
            a.push_back(i - '0');
        for(auto i:s2)
            b.push_back(i - '0');

        reverse(ALL(a));
        reverse(ALL(b));

        vector<int> result = multiply(a, b);

        int carry = 0;
        rep(i, 0, result.size())
        {
            result[i] += carry;
            carry = result[i] / 10;
            result[i] %= 10;
        }
        reverse(ALL(result));
        bool zero = true;
        for(auto i : result)
        {
            if(i == 0 && zero)
                continue;
            zero = false;
            cout << i;
        }
        if(zero)
            cout << "0";
        cout << "\n";
    }
    return 0;
}