題目連結：
題目大意：
給定兩個不超過 ２ ^ １７ 位數長的數字，求兩者的乘積。
範例輸入：
0
5
11
12
範例輸出：
0
132
解題思維：
由於本人對快速傅立葉變換（FFT）還不甚理解，因此就不會講得太深入。
FFT 在大數乘法的原理即是將兩個欲相乘的數字，先將兩數寫成多項式的形式（這部分不是 FFT 包含的範圍），例如，１２３就寫成 ３ ＋ ２ｘ ＋ ｘ ^ ２ 。
而因為 Ｎ 次多項式可以由 Ｎ ＋ １ 個值決定出來（見拉格朗日插值法），而 FFT 此時的用途即是將上面的 Ｎ 次多項式轉成 Ｎ ＋ １ 個值所組成的「向量」。其幾何意義類似於把此多項式函數 ｘ ＝ ０ ～ ２π 的部分拉到一個虛數平面單位圓上繞一圈，然後從 ｘ ＝ ０ 開始，每一次加上 ω 弧度（ω ＝ ２π ÷ Ｎ）將 ｘ 代入多項式裡求值。（求出來的值也因此是複數）
而快速傅立葉變換用了分治法（Divide and Conquer）的精神，快速地將這 Ｎ ＋ １ 個值求出（詳情參見上面提及的大大們的文章）。
當兩個數字皆各自轉為兩個 Ｎ ＋ １ 個值組成的向量之後，將同項次的地方乘在一起（類似內積，但是結果不用全部加總）。因此得到一個新的 Ｎ ＋ １ 項的向量。
然後，再將這個新向量利用反快速傅立葉變換（IFFT）轉回普通的多項式表達式。最後再將此新多項式變回一般的十進位數字，即是所求。
但是注意，FFT 只能運用在 Ｎ 是 ２ ^ ｋ －１（ｋ 為正整數）的情況下使用。因此對於長度不是 ２ ^ ｋ－１ 的數字，要將其補到 ２ ^ ｋ－１ 位數長。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
