MTT

~~标题是我乱起的名字~~。 在做某题时受到了启发，想出了一种之前没听说过的 MTT，在某谷上一问发现有人[和我想的一样](https://www.luogu.com.cn/blog/PD-qed/gao-jing-du-duo-xiang-shi-sheng-fa-di-ling-yi-zhong ......

# 任意模数多项式乘法 > 前言：\ > 在教练讲的时候脑子并不清醒，所以没听懂。后来自己看博客学会了，但目前只学了一种方法：可拆系数FFT。为了方便日后复习，决定先写下这个的笔记，关于三模数NTT下次再补。 > > 建议：准备好演算纸和笔，本篇含有大量推算部分。 > > 注：本篇文章是本蒟写的，d ......

### 三模数 NTT 常数大、速度慢、精度高是它的特点。 在考虑三模数 NTT 之前先考虑一下中国剩余定理吧。 已知 $$ \begin{cases} x\equiv x_1(\bmod m_1)\\ x\equiv x_2(\bmod m_2)\\ x\equiv x_3(\bmod m_3)\ ......