在oi wiki上看到了CNTT后，忍不住想试试。
CNTT的原理：\(\mathbb{Z}_p^*\) -> \(\mathbb{Z}_{p^2-1}^{\mathbb{C}*}\)
（也不知道是不是这个符号，就这么看吧
我们令 \(j^2=x\)，其中 \(x\) 是 %p 下的一个二次非剩余。由于我们只要做 \(2^n\) 长度的变换，\(x\) 不用是原根。
这时，在 %p 的复数中找一个 \(z\) 使 \(z^{\frac{p^2-1}{2}} \equiv -1 \pmod p\)，设 \(p=k \cdot 2^n\)，则 \(z^{\frac{n+1}{a}}\) 就是我们要的 \(a\) 次“原根”。
可以证明，CNTT能应用的变换长度是 \(p^2-1\) 的因数，因此 \(p\) 为 \(2^k-1\) 型素数时能取得和 \(2^k+1\) 型素数差不多的变换长度。
某谷的提交记录显示，CNTT常数是普通NTT的3~4倍（无优化的情况下），甚至不如FFT。
CNTT 4.56s / 56.52MB / 2.14KB C++14 (GCC 9) O2
CNTT 4.61s / 56.51MB / 2.14KB C++14 (GCC 9)
NTT 1.67s / 32.57MB / 1.69KB C++14 (GCC 9)
FFT 1.99s / 104.60MB / 1.56KB C++14 (GCC 9)
这里CNTT的模数是 \(998244353\)，使用 \(j^2=3\)，\(2^{24}\) 次单位根是 \(0+125038983j\)。
标签：KB,GCC,14,MB,C++,CNTT From： https://www.cnblogs.com/x383494/p/17280059.html