O(1) 逆元的 (理论意义上) 比较健康的做法

Elegia · 2023-07-29 12:48:52 · 个人记录

备份一下这个做法, 省得以后反复跟别人解释了.

正如分块给出的实际上是一个 O(n^{1/k}) 修改 - O(k) 查询的结构, 这里给出的是一个 O(X^{1/k}) 预处理 - O(k) 查询的结构.

准确的说, 我们求的不止是逆元, 而是 ax + by = \gcd(a,b) 的一组 x,y.

观察. 对于非零正整数 a, b < X, 存在整数可逆矩阵 M\in \mathrm{GL}_2(\mathbb Z) 使得

且矩阵的元素的绝对值 $\| M\|_\infty <X^{1/2}$.

证明. 鸽笼原理足够, 但其实有一个更加算法化的证明是分析 Euclid 算法的执行过程, 这里略去. \square

推论. 对于非零正整数 a, b < X 以及参数 B\leq X, 存在整数可逆矩阵 M\in \mathrm{GL}_2(\mathbb Z), 满足

证明. 对于 a, b, 先取 a_0 = \lfloor aB/X\rfloor, b_0 = \lfloor bB/X\rfloor. 对 a_0, b_0 取出上述构造的矩阵 M, 满足 M (a_0, b_0) 有一个分量不超过 B^{1/2}, 并且对于 M 的各分量也满足.

那么对于 M(a,b) 来说, 那个分量的大小可以被 M(a_0,b_0) \cdot B 再加上 a,b 和 a_0,b_0 之间 O(B/X) 的误差所控制. 总的来说, 误差就是 < 3X/B^{1/2} 的. \square

显然, 上述的推论可以很容易的转换成一个算法.

处理阶段. 选定 B, 预处理所有 a,b<B 的 M 以及 a,b<3B 时候的答案. 时间是 \tilde O(B^2) 的.

查询阶段. 利用上述推论的构造:

• 不断在 \max(a, b)\geq 3B 的时候将一个数从 X 变成 X \cdot 3B^{-1/2} 大小, 然后再做一次辗转相除把另一个数也变小.
• 直到当 a,b < 3B 的时候, 直接查表得到答案.

时间是 O(\log X / \log B) 的.

点评. 这个做法和 half-gcd 的关系某种意义上就类似于分块维护 操作 - 查询 和线段树的关系. half-gcd 的重点在于发现 推论 的部分是可以分治计算下去的, 这可以得到 整数 / 有限域上多项式 的辗转相除法的 O(\ell \log^2 \ell) 算法.