TIOJ 1064：A*B Problem

TIOJ 1064：A*B Problem

題目大意：給 $a$ 和 $b$，輸出 $a \times b$。($a, b$ 可能到幾百萬位)

解法：$\text{FFT...}$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using CPX = complex<double>;

const double pi = acos (-1);
const int base = 10000;
const int Len = 4;

string s1, s2;
int n, m, siz;
vector<CPX> w, a, b;

int turn (string s) {
    int re = 0;
    for (int i = s.size() - 1; i >= 0; i--)
        re = re * 10 + s[i] - '0';
    return re;
}

void init() {
    n = s1.size() / Len + (s1.size() % Len != 0);
    m = s2.size() / Len + (s2.size() % Len != 0);
    siz = 1 << (__lg (max (n, m)) + 2);
    w = vector<CPX>(), w.resize (siz);
    a = vector<CPX>(), a.resize (siz);
    b = vector<CPX>(), b.resize (siz);
    for (int i = 0; i < siz; i++)
        w[i] = {cos (2 * pi*i / siz), sin (2 * pi*i / siz) };
    reverse (s1.begin(), s1.end());
    reverse (s2.begin(), s2.end());
    for (int i = 0; i < n; i++)
        a[i] = turn (s1.substr (i * Len, Len));
    for (int i = 0; i < m; i++)
        b[i] = turn (s2.substr (i * Len, Len));
}

vector<CPX> fft (vector<CPX> v, int ty) {
    int rev[siz] = {};
    for (int i = 0; i < siz; i++) {
        rev[i] = rev[i >> 1] >> 1;
        if (i & 1)
            rev[i] |= siz >> 1;
    }
    for (int i = 0; i < siz; i++) {
        if (i < rev[i])
            swap (v[i], v[rev[i]]);
    }
    for (int len = 2; len <= siz; len <<= 1) {
        int half = len >> 1;
        for (int i = 0; i < siz; i += len) {
            for (int j = 0; j < half; j++) {
                CPX t = v[i + half + j] * CPX (w[siz / len * j].real(), ty * w[siz / len * j].imag());
                v[i + half + j] = v[i + j] - t;
                v[i + j] += t;
            }
        }
    }
    if (ty == -1) {
        for (int i = 0; i < siz; i++)
            v[i] /= siz;
    }
    return v;
}

void solve() {
    cin >> s1 >> s2;
    if (s1 == "0" || s2 == "0") {
        cout << "0\n";
        return;
    }
    init();
    a = fft (a, 1);
    b = fft (b, 1);
    for (int i = 0; i < siz; i++)
        a[i] *= b[i];
    a = fft (a, -1);
    vector<LL> ans;
    for (int i = siz - 1; i >= 0; i--) {
        LL num = round (a[i].real());
        if (!ans.size() && num == 0)
            continue;
        ans.push_back (num);
    }
    reverse (ans.begin(), ans.end());
    LL last = 0;
    for (int i = 0; i < ans.size(); i++) {
        ans[i] += last;
        last = ans[i] / base;
        ans[i] %= base;
        if (i == ans.size() - 1 && last)
            ans.push_back (0);
    }
    cout << ans.back();
    for (int i = ans.size() - 2; i >= 0; i--)
        cout << string (Len - to_string (ans[i]).size(), '0') << ans[i];
    cout << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！