看到 FFT，肯定有很多人崩溃了，其实没那么难，很容易就能懂。首先，我们需要了解复数。
众所周知，\(\sqrt 1=\pm 1,\sqrt 4=\pm 2\)。那么，\(\sqrt {-1}\) 是多少呢？肯定不是 \(1\)，因为 \(1^2=1\)，当然也不是 \(-1\)，因为 \((-1)^2=1\)。所以我们定义 \(i\) 表示 \(\sqrt {-1}\)。那么，\(\sqrt {-4}=\pm 2i\)。一个复数就形如 \(a+bi\)，它的共轭复数是 \(a-bi\)。
我们先看看，复数的四则运算分别长啥样。
加法：\((a+bi)+(c+di)=(a+c)+(b+d)i\)，很简单。
减法：\((a+bi)-(c+di)=(a-c)+(b-d)i\)，也很简单。
乘法：\((a+bi) \times (c+di)\) 是什么呢？可以用乘法分配律拆开，\((a+bi) \times (c+di)=a \times c+a \times di+bi \times c+bi \times di=(a \times c-b \times d)+(a \times d+b \times c)i=(ac-bd)+(ad+bc)i\)。
除法：因为分母是复数，所以我们需要把它乘一个共轭的复数，根据平方差公式，分母就变成了实数，然后就很简单了。\(\frac{a+bi}{c+di}=\frac{(a+bi)(c-di)}{(c+di)(c-di)}=\frac{(ac+bd)+(bc-ad)i}{c^2+d^2}=\frac{ac+bd}{c^2+d^2}+\frac{bc-ad}{c^2+d^2}i\)。
整数可以用数轴表示，复数呢？因为它是二维的，所以可以用一个平面表示，也就是复平面。\(a+bi\) 在复平面上所表示的点是 \((a,b)\)，这个复数的模长是它到原点 \((0,0)\) 的距离，也就是 \(\sqrt {a^2+b^2}\)，幅角是 \((a,b)\) 到 \((0,0)\) 这条线段的底角。两个复数相乘，规则是：模长相乘，幅角相加，接下来我们证明。
模长相乘：\(\sqrt {{(ac-bd)}^2+{(ad+bc)}^2}=\sqrt {a^2c^2-2abcd+b^2d^2+a^2d^2+b^2c^2+2abcd}=\sqrt {a^2c^2+a^2d^2+b^2c^2+b^2d^2}=\sqrt {a^2+b^2} \times \sqrt {c^2+d^2}\)。
幅角相加：这需要用到三角函数的和角公式，可以查一查。
那么，\(1\) 的 \(n\) 次方根分别是多少呢？一个模长的 \(n\) 次方是 \(1\)，它只能是 \(1\)，所以我们可以以原点为圆心，\(1\) 为半径长度，画一个圆。\(1\) 的 \(n\) 次方根也可以叫做 \(n\) 次原根。那么，这些原根肯定在圆上，那么具体是多少呢？需要看幅角。
一个幅角 \(\times n\) 是 \(360^{\circ}\)。那么这个幅角的度数肯定是 \(360^{\circ} \div n\) 的整倍数，所以一共有 \(n\) 个 \(n\) 次原根。
讨论这么多关于复数的内容，该进入正题了！
首先，FFT 是干什么用的？它可以快速求多项式乘法。多项式指的是形如 \(\sum\limits_{i=0}^{n-1}x^i \times f_i\)，其中 \(x\) 只是一个符号，并不是一个数。我们可以把 \(n\) 设为 \(2^k\)，其中 \(k\) 自己定，那么剩余的空间我们可以用 \(0\) 代替。
原文：https://www.cnblogs.com/Chtholly-Girlfriend/p/FFT-Algorithm.html