取模优化

就不讲怎么减少取模了。

比较广为流传的有两种，Barrett reduction，Montgomery Algorithm。

对于固定常数模数，计算机已经优化的很好了，一般不会有太大效果（确实有，用 Barrett reduction 有时可以卡常）。

对于输入的固定模数（即不会改变），可以用一下算法优化。

Barrett reduction：

一句话总结，比较有用，比较好写

考虑对于 \(a\bmod m\)，可以用 \(a-m\lfloor \frac{a}{m}\rfloor\)，但是直接计算 \(\lfloor \frac{a}{m}\rfloor\)，由于除法的常数，并不会快。

众所周知，不能精确计算的就粗略计算，考虑除以 \(2^k\) 是快的，因为可以用位运算，于是我们考虑将 \(\lfloor \frac{a}{m}\rfloor\) 用除以 \(2^k\) 估算。

具体的，设 \(base=\lfloor \frac{2^k}{m} \rfloor\)，于是 \(\lfloor \frac{a}{m}\rfloor\) 可以粗略计算为 \(\lfloor \frac{base*a}{2^k}\rfloor\)。

优点是简洁好写，缺点是有一定错误率，且需要用 __int128。

错误率：显然，\(\lfloor \frac{base*a}{2^k}\rfloor \le \lfloor \frac{2^k}{m} \rfloor\) 对于 \(k\) 取 \(64\) 时，\(m\) 在 \(10^9\) 左右的模数，极限值域在 \(10^{18}\) 时，用 __uint128_t 存储 \(base\)，在测试了 \(10^{10}\) 组纯随机数据中，\(\lfloor \frac{2^k}{m} \rfloor - \lfloor \frac{base*a}{2^k}\rfloor \le 1\)，可以加上判断来减掉误差（虽然会变慢）。

Montgomery Algorithm：

一句话总结，卵用没有。

考虑对于加减法，显然可以用判断来代替取模，对于乘法（\(ab \bmod m\)），我们考虑优化。

这里我们需要 \(m\perp 2\)。

设 \(R=2^k > m,a'=aR \bmod m,b'=bR \bmod m\)。

显然有 \(abR \equiv a'b'R^{-1} \pmod m,a'R^{-1}\equiv aR^2 \pmod m,b'R^{-1}\equiv bR^2 \pmod m\)，而 \(R^2 \bmod m\) 是可以预处理的，所以我们只要能够快速求出 \(xR^{-1}\bmod m\) 就可以快速求出 \(a',b'\)，进而求出 \(abR,ab\)。

如何求出 \(xR^{-1}\) ，考虑求最小的 \(k\) 满足 \(R | x+km\)，在将 \(R\) 除掉即可，\(k\pmod -xm^{-1} \pmod R\)，提前处理 \(m^{-1} \bmod R\)即可。

优点是不用 __int128，并且实现精细的话可能更快，缺点是必须精细实现，要封装 \(modint\) 来减少转换，细节较多（反正我调了一下午还不如本地动态模数暴力快，提交比固定模数略慢）。

唯一的作用没准就是做模板题 at_arc148_f。

速度测试以后会补，有简单的本地评价： Barrett reduction 未加判断。

固定模数： \(默认=Barrett reduction<Montgomery Algorithm\)

非固定数： \(Barrett reduction<默认<Montgomery Algorithm\)

学校 OJ 上固定模数 Montgomery Algorithm 略慢于默认，Barrett reduction 快于默认。

Barrett reduction，Montgomery Algorithm 都不会受模数是否固定影响。