首页 > 笔记 > 任意模数NTT总结

任意模数NTT总结

感觉这个点子还是很不错的,记录一下。

题目:两个多项式做乘法,$n \leq 10^5, a_i \leq 10^9$

我们发现这样的最大值是$10^{9^2} \times 10^5 = 10^{23}$,好像是爆longlong的。而且不是质数没法ntt啊。

那么我们就想到选三个满足NTT性质且乘起来$ > 10^{23} $的模数分别NTT,最后中国剩余定理合并。

这只解决了后面的那个问题,怎么解决炸longlong的问题呢。这需要一些特殊技巧

我们得到的同余式是这样的

$$
\left\{
\begin{aligned}
Ans &\equiv a_1 \pmod{m_1}\\
Ans &\equiv a_2 \pmod{m_2}\\
Ans &\equiv a_3 \pmod{m_3}
\end{aligned}
\right.
$$

先用中国剩余定理合并前两个同余式,得到

$$
\left\{
\begin{aligned}
Ans &\equiv A \pmod{M}\\
Ans &\equiv a_3 \pmod{m_3}
\end{aligned}
\right.
$$

把ans拆开

$$Ans=kM+A=k'm_3+a_3$$

假如在$\pmod {m_3}$的意义下的话,那么有(消掉$k'm_3$)

$$kM \equiv a_3 - A \pmod {m_3}$$

也就是说

$$k \equiv (a_3 − A) M^{−1} \pmod {m_3}$$

求出k之后代入$Ans = kM + A$,这样就可以直接模任意数了。

注意在中国剩余定理合并的时候需要快速乘。

2009国家集训队论文:骆可强:《论程序底层优化的一些方法与技巧》

提交地址:luogu模板


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×