HDU 1402 大數乘法：FFT 快速傅里葉變換多項式乘法 C++ 實現

問題背景

超大整數乘法（長度 ≤ 10⁵），普通大整數/模擬乘法 O(n²) 超時。FFT 將整數視為多項式，利用複數根單位性質在 O(n log n) 完成卷積。

FFT 核心步驟

1. 字符串逆序存入複數數組：x[i] = s[len-1-i] - '0'
2. 長度擴展至 2 的冪次 N ≥ 2*max(len1,len2)
3. DFT：fft(a, N, 1)、fft(b, N, 1)
4. 點值乘法：c[i] = a[i] * b[i]
5. IDFT：fft(c, N, -1)，結果除以 N
6. 進位處理：實部四捨五入取整，處理進位
7. 輸出最高非零位到最低位

關鍵代碼結構

struct Complex { double x, y; /* 運算符重載 +,-,* */ };
void change(Complex y[], int len) { /* 位逆序置換 */ }
void fft(Complex y[], int len, int on) {
    change(y, len);
    for (int h=2; h<=len; h<<=1) {
        Complex wn(cos(-on*2*PI/h), sin(-on*2*PI/h));
        for (int j=0; j

進位與輸出
for (int i=0;i0 && sum[len]==0) --len;
for (int i=len; i>=0; --i) putchar(sum[i]+'0');

複雜度與精度
時間 O(N log N)，N ≤ 2²⁰ ≈ 10⁶。雙精度浮點誤差可控，+0.5 四捨五入修正。Java BigInteger 內部亦用類似算法。

模板適用場景

大整數乘法/加法/減法
多項式乘法/模運算
字符串模式匹配（含通配符）