注意
由于蒟蒻实在太弱了~^_^~暂时无法完成证明，仅能写出简单版总结
与FFT的区别
(NTT)与(FFT)的代码区别就是把单位根换成了原根，从而实现无精度误差与浮点数的巨大常数
原根具有单位根的所有特点，原根是在特定模数下的定义
对于模数(p)，原根(g)满足：(~_{i=0}^{p-1}g^i (mod~p))均不同
用(type=1,g^{frac{p-1}{2*mid}}；type=-1,dfrac{1}{g^{frac{p-1}{2*mid}}})代替单位根
最后得到的值除一下(limit)
原根
快速求原根：对于模数(p)分解质因数，(p-1=p_1^{k_1}...p_n^{k_n})，原根(g)满足(~_{i=1}^n g^{frac{p-1}{p_i}}≠1(mod p))
求原根就直接分解(p-1)，然后(1)~(p)枚举原根就行，通常原根很小，所以能快速求出
(w=g^{frac{p-1}{2*mid}})