数论来力……证明之类的也许会大挂。
或者其实还好，在参考别人的证明思路之后。
Pre
注意到 FFT 中需要复数计算，原因在于涉及到了单位复数根。
有没有替代品？复数域（这是包含实数和虚数的）内暂时没有。
不过我们可以考虑在模意义下找一个。
阶与原根
对于一个正整数 \(n\)，能满足 \(g^k \equiv 1(\mod n)\) 的最小 \(k\) 是 \(g\) 模 \(n\) 的阶，记作 \(\delta_m(g)\)。
阶的一条性质：若 \(g^k\equiv 1(\mod m)\)，则 \(\delta_m(g) \mid k\)。
证明则是把 \(k\) 除掉 \(\delta_m(g)\)，得到 \(g^{q\delta_m(g)+r}\equiv 1(\mod m)\)，然后 \((g^{\delta_m(g)})^q\equiv 1(\mod m)\)，所以若 \(r\ne 0\) 就和阶的最小性矛盾。
对于一个正整数 \(n\)，存在一个 \(g\) 使得 \(\gcd(g,n)=1\) 且 \(\delta_m(g)=\varphi(n)\)，则 \(g\) 称作模 \(n\) 的原根。
下面 \(p\) 为模数。
由于我们要用到不同 \(n\) 下的单位根，我们考虑给原根也配个类似的出来：\(g_n=g^{\frac{p-1}{n}}\)，其中 \(n \mid p-1\)，此时 \(g_n\) 是 \(p\) 的一个原根，且刚好和这个 \(\omega_n\) 意义类似。
证明的话考虑 \(g^k\)，其阶为 \(\frac{p-1}{\gcd(p-1,k)}\)（原因考虑欧拉定理，这里也可以说是费马小定理，把这玩意儿弄到上界），然后我们想要 \(n\) 是这个原根的阶，就可以考虑构造；发现 \(\frac{p-1}{\gcd(p-1,(p-1)/n)}=\frac{p-1}{(p-1)/n}=n\)，所以就取 \(g^{\frac{p-1}{n}}\)。
如果 \(n\nmid p-1\)，发现要求 \(\frac{p-1}{\gcd(p-1,x)}=n\)，也就是说 \(\gcd(p-1,x)=\frac{p-1}{n}\)，那这玩意儿就不是整数了，显然不合法。
然后我们看这个 \(g_n\)，它满足单位根的性质吗？
- \(\omega_n^0,\cdots,\omega_n^{n-1}\) 两两不同。
单位根定义，显然。
证明考虑取 \(g_n^i \equiv g_n^j(\mod p)\)，然后两边做差发现同样违背阶得最小性。
- \(\omega_{dn}^{dk}=\omega_n^k\)
消去引理。同理，和单位根那一模一样。
- \(\left\{(\omega_n^0)^2,\cdots,(\omega_n^{n-1})^2\right\}=\left\{\omega_{n/2}^0,\cdots,\omega_{n/2}^{n/2-1}\right\}\)
折半引理，这里比较棘手。
首先说明 \(g_n^k=g_n^{k+n/2}\)，考虑两边分别平分，有 \(g_n^{2k}=g_{n}^{2k+n}\)。显然其中 \(g_n^n=(g^{\frac{p-1}{n}})^{n}=g^{p-1}=1\)，故成立。
然后就说好了，这玩意儿显然了，也不棘手。
- \(\sum\limits_{k=0}^{n-1}(\omega_n^d)^k=\frac{(\omega_n^d)^n-1}{\omega_n^d-1}\)，要求 \(d\nmid n\)
有没有可能我们最先在整数域上学的等比数列这玩意儿。
现在我们说明了在模意义下原根跟单位根有一样好的性质，也能拿来算多项式乘法.
而这个东西由于涉及到上面一堆数学，于是就成了 NTT（快速数论变换）。
式子基本一致，把 \(\omega_n\) 换成 \(g_n\) 即可。
注意我们要求 \(n \mid p-1\)，而 \(n=2^k,k\in\mathbb{N_+}\)，所以你随便搞个 \(p-1\) 是 \(2^k\) 倍数的模数就好了，如典中典的 \(998244353=2^{17}\times 17\times 7+1\)，且存在一个原根 \(g=3\)。
代码咕了。