您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 2179 FFT 快速傅立葉：大整數乘法經典實作

編輯：關於C++

題目大意

給定兩個 n 位十進制整數 x, y (n ≤ 60,000)，求 x × y。

核心思路：FFT 加速多位數乘法

將整數視為係數多項式：

x = Σ aᵢ × 10ⁱ, y = Σ bᵢ × 10ⁱ

乘積係數 cₖ = Σ aᵢbₖ₋ᵢ → 卷積，FFT 可在 O(n log n) 完成。

實作關鍵點

位元反序：輸入字串從低位到高位存入陣列
進位處理：IFFT 後每位取整，逐位處理進位（模 10，進位除 10）
長度計算：結果最長 2n 位，FFT 長度取 ≥ 2n 的 2 的冪
精度保證：單位係數 ≤9，卷積峰值 ≤ 9×9×60000 ≈ 4.9×10⁶，雙精度誤差 < 0.1，四捨五入安全

完整程式碼 (C++)

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

const double PI = acos(-1.0);

struct Complex {
    double x, y;
    Complex(double _x=0, double _y=0): x(_x), y(_y) {}
    Complex operator+(const Complex& o) const { return Complex(x+o.x, y+o.y); }
    Complex operator-(const Complex& o) const { return Complex(x-o.x, y-o.y); }
    Complex operator*(const Complex& o) const { return Complex(x*o.x - y*o.y, x*o.y + y*o.x); }
};

void fft(vector<Complex>& 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);
        Complex wlen(cos(ang), sin(ang));
        for (int i=0; i<n; i+=len) {
            Complex w(1, 0);
            for (int j=0; j<len/2; ++j) {
                Complex u = a[i+j];
                Complex v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w = w * wlen;
            }
        }
    }
    if (invert) for (auto& x : a) x.x /= n, x.y /= n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    string sx, sy; cin >> sx >> sy;
    
    // 低位在前存入
    vector<double> a(n), b(n);
    for (int i=0; i<n; ++i) a[i] = sx[n-1-i] - '0';
    for (int i=0; i<n; ++i) b[i] = sy[n-1-i] - '0';
    
    int N = 1;
    while (N < 2*n) N <<= 1;
    a.resize(N); b.resize(N);
    
    vector<Complex> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fft(fa, false); fft(fb, false);
    for (int i=0; i<N; ++i) fa[i] = fa[i] * fb[i];
    fft(fa, true);
    
    // 進位處理
    vector<int> ans(N);
    for (int i=0; i<N; ++i) ans[i] = (int)(fa[i].x + 0.5);
    for (int i=0; i<N; ++i) {
        if (ans[i] >= 10) {
            ans[i+1] += ans[i] / 10;
            ans[i] %= 10;
        }
    }
    
    // 輸出（高位在前，跳過前導零）
    int pos = N-1;
    while (pos > 0 && ans[pos] == 0) --pos;
    for (int i=pos; i>=0; --i) cout << ans[i];
    cout << '\n';
    return 0;
}