在某种意义上说，应该属于 的一种优化。
——因而必备知识肯定要有 啦...
如果不知道 的大佬可以走这里
在 中，为了能计算单位原根 ，我们使用了 的 库中的 函数，所以我们无法避免地使用了 以及其运算。
但是，众所周知的， 的运算很慢，并且，我们的虚数乘法是类似于下面这种打法：
显然，一次虚数乘法涉及四次 的乘法。
并且在运算过程中，会有大量的精度丢失，这都是我们不可接受的。
然而问题来了：我们多项式乘法都是整数在那里搞来搞去，为什么一定要扯到浮点数。是否存在一个在模意义下的，只使用整数的方法？——Tiw_Air_OAO
想一想我们使用了单位复根的哪些特性：
- 个单位根互不相同，且
那么我们能否在 模意义 下找到一个性质相同的数？
这里有一个同样也是 某某根 的东西，叫做 原根 。
对于素数 ， 的原根 定义为使得 互不相同的数。
仔细思考一下，发现 原根 与 单位复根 很像。
同理，我们再定义 ，这样 就与 长得更像了...
但是，必须在 满足与 同样的性质时，我们才能等价替换。
现在，我们检验原根在模意义下是否满足与单位复根同样的性质：
- 由幂的运算立即可得
- 由幂的运算立即可得
- ，因为 且由原根定义 ，故
- 由原根的定义立即可得
发现原根可以在模意义下 完全替换 单位复根。
这就是 了。
但是，这样的方法对模数会有一定的限制
令 ， 为奇数，则多项式长度必须
至于模数以及其原根，没有必要来死记，为什么？
我们程序员就应该干我们经常干的事情——打表可得...
以下是参考代码：
假如题目中规定了模数怎么办？还卡 FFT 的精度怎么办？
有两种方法：三模数 NTT 以及 拆系数 FFT (MTT)
我们可以选取三个适用于 的模数 进行 ，用中国剩余定理合并得到 的值。只要保证 就可以直接输出这个值。
之所以是三模数，因为用三个大小在 左右模数对于大部分题目来说就足够了。
但是 可能非常大怎么办呢？难不成我还要写高精度？其实也可以。
我们列出同余方程组：
用中国剩余定理合并前两个方程组，得到：
其中的 满足
然后将第一个方程变形得到 ，代入第二个方程，得到：
令 ，则 。
再将上式代入回 ，得 。
又因为 ，所以 。
也就是说 。
然后，我们完美地解决了这个东西。
接下来是代码：