作者 JustPureH2O 深受日本轻小说文化的洗礼，特地模仿轻小说中常见的设定，为本文安上了“特典”二字。不了解轻小说的读者可以将这个词理解为“具有特殊意义的篇目”。
我曾在《信息竞赛 高级数学》中介绍过“世界上最优雅的算法”——FFT（快速傅里叶变换），并给出了洛谷 FFT 模板题的代码实现。在竞赛退役两周年（说是两周年不大合适，因为我的退役是 2024 年 11 月底，距两周年仍有一个半月）、本站建站三周年之际，我想用一篇具有特殊意义的文章来纪念之。
关于这篇纪念文章的内容，我想了比较长的时间。起初几乎确认要写一篇科技类的文章（而非生活类），但由于大学不给发手机（即断网状态），无法搜集到互联网资料。因而我只能从已有的文章出发，选取已有的素材。我对素材的第一反应大概是我时刻挂在嘴边，位列本站标签排行榜第五的“线性代数”，但是又因为 《线性代数》一书不在近前，而且并无关于线代的新点子出现。一日 C 程序设计课上，教员讲起数据类型，说起大数的数组存储，偶然想起洛谷“大数乘法”背后的 FFT 算法。重读《信息竞赛 高级数学》一文后，发现这篇文章大抵是水完洛谷模板题后照本宣科的产物，当时的我并未真正理解 FFT 的内涵，处于所谓“眼睛会了，脑子不会”的状态。这驱使我将 FFT 作为本篇特典文章的探讨对象。尽管如前所述，我不甚理解 FFT 的全貌，但幸亏我仍记得它的“点值表示”“系数表示”，高中所学的“复数”“单位根”尚未全忘，利用午后一个半小时的自习课时间，从前述的几点核心体系出发，重新复现 FFT 这一经典的优雅算法，并在下面给出“大数乘法”的实现方案。
由于大学不给开网（再次强调），本文不再对 FFT 的历史进行阐述，若确需了解，请参阅《信息竞赛 高级数学》一文。
谨以此篇，献给本站。
函数卷积与大数乘法#
我们知道，FFT 能在 的时间复杂度下解决多项式函数的卷积问题，即两函数的相乘问题。例如此时有函数 ，定义卷积函数 ，简单运算可得：
那有人会问，函数卷积和我们将要解决的大数乘法之间有什么必然联系吗？尽管他们看起来都涉及到“乘法”这一核心概念。
这个问题的解答需要回到进位制的概念：十进制逢十进一。举个例子，五位数 其实就是 。发现什么没有？我们令函数 ，那么有 ，据此可以表示出两个乘数对应的函数，函数相乘，再代入 即可得到乘法结果。这样就架起函数卷积和大数乘法间的桥梁了。
但按项相乘是不能满足我们对于算法高效性的追求的：不妨回望你得到这个结果的心路历程——将 拆成项 和 ，然后分别与 相乘后求和、合并同类项、整理后得到三次多项式 。笔者也不例外，因为这是最符合人类计算思维的方法，但我们现在来考察这种做法在计算机上的局限性。
按最坏情况算， 均为满的 次多项式，相当于 的 项（包括常数项）都要分别与 中的 项相乘，需要做 次乘法运算，因而我们说这种方法的时间复杂度是 的。这样的时间复杂度在很多追求效率的应用场景中都是不可接受的，FFT 将大数乘法问题求解优化至 ，大大提高了执行效率。
点值表示与系数表示#
为了优化我们那朴素的算法，首先需要引入两个概念：点值表示和系数表示。
顾名思义，我们用关于 的多项式来表示函数，形如 的表示方式称作系数表示法，函数的系数 出现在解析式中。
同时，考虑到函数的几何意义。在函数图像上取出若干点组成点集 ，这 个点可唯一确定一个 次多项式函数，这就是点值表示法。
假如此时有两个点集 和 ，分别对应两函数的点值表示，求解卷积函数的点值就变得非常简单了，只需将两个具有相同 坐标点的纵坐标相乘即可。 个点的 相乘得到卷积函数上的点，这个操作的时间复杂度显然是 。
那么我们急需找到一个高效的点值-系数互转算法来优化掉剩余的部分。实际上，FFT 和 IFFT（FFT 逆运算）优化卷积问题本质上就是优化系数表示与点值表示的互转操作。这可谓 FFT 最精髓的部分。
快速傅里叶变换#
假设此时有多项式函数：
可以将函数二分为奇函数和偶函数部分，分别用 表示，即 ，常数项属于 。以 为例，拆分后 。同理，有：
两函数中的幂指数是相互间隔 的，我们让他们连续排列。若此时有函数 对应 的处理结果，我们希望达到如下效果：
这么做的深意就在于：新的 和 就变成了两个新的多项式，类推下去， 也可以分为两个其他的多项式，最高次幂再除以二，简化了计算——计算全部，仅需计算一半，这是经典的二分法思维。
要根据 构造这两个函数，不难发现 ，则 。
要计算 ，就要计算 和 。根据奇函数（偶函数）的性质，代入 值后，先求出一个 ，再代入 ，我们可以不必计算，直接可得结果是 （）。
单位根#
我们在高中接触过复数的计算法则，其中有一节的内容“复数与三角表示”被标注为选学，节末给出了著名的棣莫弗定理，也就是我们将要讨论的单位根。
在实数范围下，我们说方程 的根是 ，方程 的根是 。但当我们把讨论范围拓宽到复数范围时，结果就不同了。
考虑方程 的根， 是显然的。如果稍加思索，你会发现 也是可行的（，即虚数单位）。事实上，当我们检视一个横为实数轴、纵为虚数轴的复平面时，方程 的根会将复平面上的单位圆平均分为 份，记作 （注意此时上标不代表幂）。特别地，。
如果对两个复数进行相乘，得到的结果复数在复平面上也有奇妙的性质。它的模长是两个乘数复数的积、方向向量与实数正半轴的夹角（辐角）为两复数辐角之和（模长相乘，辐角相加）。结合单位根模长为 、等分单位圆以及周期性，可以导出如下几条法则：
快速傅里叶变换
对多项式 f(x)=\sum_{i=0}^{n-1}a_ix^i\in X_{n-1} ，不失一般性 的，设 （由于在多项式的乘法中我们可以将一个多项式等价地看作是次数更高的高
次项系数均为零的多项式，故可以将 n 看作第一个大于等于它的 2 的整数次幂），考虑按
a_i 下标的奇偶性 将 f(x) 中的项分为两部分，即
令
则 带入 可得
带入 可得
观察 (1),(2) 两式的结构，我们只需要求出 即可 求出 (1),(2) 两式的值，进而再经过类似的步骤，我们可以以 的时间复杂
度将问题继续转化为求 ……最
终问题被转化为求 故以 的时间复杂度可以求出 ，进而可以以
的时间复杂度求出所有的 ，即我们以 的时间复杂度将 f 的系数表示法转化为了点值表示法
