前置
根据快速傅里叶变换，可以在 \(\Theta(n \log n)\) 的时间计算卷积。但是由于用到了复数及三角函数，具有精度误差，且不方便取模。
于是考虑快速傅里叶变换在数论上的实现，避免了精度误差，支持了取模运算。
引入概念原根：
阶
定义
由欧拉定理可知，对 \(a\in \mathbf{Z}，m\in\mathbf{N}^{*}，若 (a,m)=1，则 a^{\varphi(m)}\equiv 1\pmod m\)。
因此满足同余式 \(a^n \equiv 1 \pmod m\) 的最小正整数 \(n\) 存在，这个 \(n\) 称作 \(a\) 模 m 的阶，记作 \(\delta_m(a) 或 \operatorname{ord}_m(a)\)。
性质
\(a,a^2,\cdots,a^{\delta_m(a)}\) 模 \(m\) 两两不同余。
若 \(a^n \equiv 1 \pmod m\)，则 \(\delta_m(a)\mid n\)。
原根
定义
设 \(m \in \mathbf{N}^{*}，g\in \mathbf{Z}\)。 若 \((g,m)=1\)，且 \(\delta_m(g)=\varphi(m)\)，则称 \(g\) 为模 \(m\) 的原根。
即 \(g\) 满足
\(\delta_m(g) = \left| \mathbf{Z}_m^* \right| = \varphi(m)\)。当 \(m\) 是质数时，我们有 \(g^i \bmod m,\,0 \lt i \lt m\) 的结果互不相同。
性质
\(g\) 是模 \(p\) 的原根，\(g_n^k=g^{\frac{p-1}{n}k}\)。
指数性
\[\begin{aligned} g_n^k g_n^m &\equiv g^{\frac{p-1}{n}k} g^{\frac{p-1}{n}m} \\ &\equiv g_n^{k+m} \pmod p \end{aligned} \]周期性
\[\begin{aligned} g_n^{k} &\equiv g_n^{k} \times 1 \\ &\equiv g_n^k g_n^{\varphi(p)} \\ &\equiv g_n^k g_n^{p-1} \\ &\equiv g_n^k g_n^n \\ &\equiv g_n^{n+k} \pmod p \end{aligned} \]对称性
由阶的性质与：
\[(g_n^{\frac{n}{2}})^2 \equiv g_n^n \equiv 1 \pmod p \]可得：
\[g_n^{k+\frac{n}{2}} \equiv -g_n^k \pmod p \]折半性
\[\begin{aligned} g_n^{2k} &\equiv g^{\frac{p-1}{n}2k} \\ &\equiv g^{\frac{p-1}{\frac{n}{2}}} \\ &\equiv g_{\frac{n}{2}}^{k} \pmod p \end{aligned} \]可以观察到原根与复数在这里是完全等价的，故只需将快速傅里叶变换的复数部分替换为原根即可。
NTT & INTT
void NTT(ll f[],int n,int op)
{
if(n==1) return;
ll f1[n/2],f2[n/2];
for(int i=0;i<n/2;++i)
{
f1[i]=f[i<<1],f2[i]=f[i<<1|1];
}
NTT(f1,n>>1,op),NTT(f2,n>>1,op);
ll gk=1,g1=qpow(op==1?g:gi,(p-1)/n);
for(int i=0;i<n/2;++i)
{
f[i]=(f1[i]+gk*f2[i]%p)%p;
f[i+n/2]=(p+f1[i]-gk*f2[i]%p)%p;
gk=gk*g1%p;
}
}