Montgomery 取模器

· · 个人记录

好的来写个介绍×偏意识流，废话一堆，希望初学者能看懂。

众所周知，OI 中许多以计数为代表的题需要大量的取模操作，而取模操作是很慢的。一般加加减减的取模还好处理，毕竟蛐蛐 [0,2p) 或 (-p,p) 值域，随便判个大小搞回来就行。但乘法取模则是更加难过的问题——毕竟不可能真的写个类似快速乘那种 \log 次加减的屑东西。我们需要的是一些更加快速的取模算法。目前 OI 范围内比较流行的主要有两种：Barrett（巴雷特）和 Montgomery（蒙哥马利）。注意到前者相当平凡且资料较多，本文主要介绍后者。

不妨假设我们的模数是奇数 p。定义 P(x)=x\bmod p，其中 x 为有理数且分母不为 p 的倍数。现在我们有神秘正整数 r 不为 p 的倍数，它是多少我们后面再管。定义 R(x)=P(xr)，称为整数 x 的蒙哥马利形式。我们的取模器实际上维护的就是整数的蒙哥马利形式，比如这样（x,y\in[0,p)）：

  1. 已知 x，求 R(x)。

  2. 已知 R(x)，求 x。

  3. 已知 \sout{R(x)} 和 \sout{R(y)}，求 \sout{R(x\pm y)}。 有点平凡，以下无视。

  4. 已知 R(x) 和 R(y)，求 R(xy)。

现在假定我们实现了函数 R'(x)=P(\frac xr)，其中 x 为小于 p^2 的自然数。我们来看看如何运用这个东西把上面四个玩意跑出来（记 z=P(r^2)）：

一切变得如此美妙。于是现在问题的核心就是 R' 怎么求。不妨记 R'(x)=y，则 y 是方程 yr-tp=x（t 为整数）的最小自然数解。如此一来 y=\frac{tp+x}{r}。预处理 q=-\frac1p\bmod r，取 t=xq\bmod r，则得到 y 为小于 \frac{pr+p^2}r 的自然数，对这个东西微调即可。于是现在需要快速算一个东西模/除以 r 同时要求 \frac{pr+p^2}r=O(p) 即 r=\Omega(p)。不难发现取 r 为不小于 p 的 2 的幂可以很好地满足这两点。于是做完了。奇怪的小细节：懒得写逆元的话可以取形如 r=2^{2^k} 的东西然后一行牛迭搞定。

这个东西的优势是什么呢？熟悉巴雷特模乘的读者应当不难发现对于 2^{32} 以内的模数这东西运算数是可以直接飙到 2^{128} 规模的，需要形如 __uint128_t 的东西。但蒙哥马利不然，从头到尾运算都控制在 2^{64} 以内，一个 unsigned long long 就能搞定。

以上。