[ Number Theoretic Transform ] 快速數論變換)(NTT)

這也不知道怎麼說明，應該是我數學太爛的關係，直接看連結吧

• 維基百科-數論變換
• 多项式乘法运算终极版
• 从多项式乘法到快速傅里叶变换
• Morris的code

有以下幾點要注意:

1. P要是一個q*2^k+1的質數，G是P的原根
2. N(數列長度)要是2的冪次
3. (P-1)%N=0
4. 做了逆轉換後的結果為原本數列mod P的結果，所以P要夠大
5. 如果要求P是任意數的話，可以用中國剩餘定理處理

這裡有一些質數和它的原根(按質數順序由大到小排):

• 2615053605667*(2^18)+1,3
• 15*(2^27)+1,31
• 479*(2^21)+1,3
• 7*17*(2^23)+1,3
• 3*3*211*(2^19)+1,5
• 25*(2^22)+1,3

因為可能會有A*B%M的情況發生，所以需要用
long long 乘 long long 模 long long不溢位算法
只需要將code裡面所有的A*B%M的部分改掉即可

以下提供模板(bit_reverse參考自Morris):