这两个”根“在多项式乘法里面运用非常广泛。

单位根（FFT）

关于我自己对单位根的理解。

单位根其实就是一些复数，他们的模长为$1$。

所以单位根一定在单位圆上

假设一个单位根$z$的极角为$\theta$，那么我们可以将$z$表示为$\cos \theta +i \sin \theta$

数形结合考虑，从圆上某一个点做一条垂线，那么垂线长度为$\sin \theta$，垂足到原点距离为$\cos \theta$

考虑使用向量模长验证，$|z|=\sqrt{\sin ^2 \theta + \cos ^2 \theta}=1$

$\omega_n^k = \cos \frac{k}{n} 2 \pi+ i \sin \frac{k}{n} 2 \pi$

感性地理解这个式子，注意到$2 \pi$为$360°$，所以这个式子的意义就是将单位圆用一些经过圆心的线分成$n$份，从$1+0i$往逆时针数$k$次，数到的线的端点所代表的复数。

于是发现四个推$FFT$所用的经典的式子都非常$naive$

$1.\omega _n^k=\omega _{2n}^{2k}$

这个代表的意思就是把单位圆分成$n$份，数$k$次，和分成$2n$份，数$2k$次所代表复数是一样的。非常智障。

也可以通过三角函数证明：

$\omega^k_n=\cos{k\over n}2 \pi +i\sin{k\over n} 2\pi =\cos{2k\over 2n}2\pi+i\sin{2k\over 2n} 2\pi=\omega^{2k}_{2n}$

$2.\omega _n^{k+{n \over 2}}=-\omega _n^k$

定义：对于复数$z=a+bi$，$-z=-a-bi$

这个也非常好理解，$n/2$代表半圈，所以这个式子的意思是从编号为$k$的复数开始走半圈，代表的复数和之前的正好相反（实部和虚部都相反）

$3. \omega _n^0=\omega _n^n =1,\omega _n^{\frac{n}{2}}=-1$

编号为$0$和编号为$n$的点代表的复数相等，都为$1+0i$，编号为$n/2$的点其实就是$1+0i$转过半圈，就是$-1+0i$

$4.\omega _n^p \times \omega _n^q = \omega _n ^ {p+q}$

复数的乘法其实像三角函数一样，设$z_1=a_1+ib_1,z_2=a_2+ib_2$

根据复数乘法定义，那么我们有$z_1 \times z_2 = (a_1 \times a_2 - b_1 \times b_2)+i(a_1 \times b_2+a_2 \times b_1)$

我们有三角函数的合角公式：

$\sin(A+B)=\sin A \cos B+\cos A \sin B$
$\cos (A+B)=\cos A\cos B-\sin A \sin B$

换元：$\alpha = \frac{p}{n} 2 \pi, \beta = \frac{q}{n} 2 \pi$

于是$\omega _n^p = \cos \alpha + i \sin \alpha$

还有$\omega _n^q = \cos \beta + i \sin \beta$

于是$\omega _n ^p \times \omega _n ^q = (\cos \alpha \cos \beta-\sin \alpha \sin \beta) + i (\sin \alpha \cos \beta+\cos \alpha \sin \beta) = \cos (\alpha + \beta)+i \sin(\alpha +\beta) = \omega ^{p+q}_n$

（吐槽一句，复数的乘法好像就是为了这个东西定义的）

这个式子要好好体会。

有了第四个式子，我们就可以再推出第三个式子：

$\omega _n ^{k+\frac{n}{2}}=\omega _n^{\frac{n}{2}} \times \omega _n^k = (-1+0i) \times \omega _n^k = -\omega_n^k$

原根（NTT）

有时候题目要求对一个大质数取模，这时就不能用单位根，要用原根。

$p$的原根是满足$g^0\%p,g^1\%p,g^2\%p...g^{p-2}\%p$恰好等于$[1,p-1]$中的所有数的最小的$g$。

现实中，可以从$2 \to p-1$枚举$g$，如果满足$g ^\frac{p-1}{p_i} !=1 \pmod p$均成立，那么我们就找到了$p$的原根。

我们称$g_n$为$n$的原根，那么我们也得到了类似于$\omega_n^k$一长串的$g_n^0,g_n^1,g_n^2, ... ,g^{n-2}_{n}$，而且他们模意义下和$[1,p-1]$中的所有数一一对应。

我们设一个素数$p=a \times 2^b+1$

有以下等价关系：$g_n=g^{\frac{p-1}{n}} \Leftrightarrow \omega_n=\cos \frac{2\pi}{n}+i\sin\frac{2\pi}{n}$。（下面证明）

并且有$g_n^k=g^{\frac{p-1}{n} \times k}$

显然有$g_n^p \times g_n^q=g^{\frac{p-1}{n} \times (p+q)}=g_n^{p+q}$。

$1.g_{2n}^{2k}=g_n^k$

显然，$g_{2n}^{2k}=g^{\frac{p-1}{2n} \times 2k}=g^{\frac{p-1}{n}k}=g_n^k$。

$2.g_n^{\frac{n}{2}}=-1,g_n^{0}=g_{n}^n=1$

显然$g_n^0=g^0=1,g_n^n=g^{p-1}=1 \pmod p$。

因为$(g_n^{\frac{n}{2}})^2=g_n^n=1$

得$g_n^{\frac{n}{2}}=\pm 1$。

又因为$g_n^n!=g_n^{\frac{n}{2}}$，且$g_n^n=1$，所以$g_n^{\frac{n}{2}}=-1$。

$3.g_n^{k+\frac{n}{2}}=-g_n^k$

上面的式子套入$p=k,q=\frac{n}{2}$，显然。