关于基于值域预处理 GCD 的一点体力活

· · 题解

前言

见 这里。

内容

做了一点微末的拓展。

从上文得知，我们有定理：

存在分解 n 的方法使得 n=abc,a\le\sqrt n,b\le\sqrt n 且 c\in \text{Prime}\ \text{or}\ c\le\sqrt n。

证明不再赘述。

接下来将给出更加一般化的形式：存在分解 n 的方法 b_1b_2...b_k 使得 \forall 1\le i\le k,b_i\le n^{1/m}\ \text{or}\ b_i\in\text{Prime}。

将指出 m 与 k 较为宽松的关系。（其实就是把 2 换成了未知数，做了一点计算而已）

令 b_1\le b_2\le...\le b_k。

我们采用类似的构造方法，考虑拿出 p=\text{minp}(n)，那么如果其可以直接乘在 n/p 表示中的 b_1 中，则应当满足如下不等式：

(\frac{n}{p})^{1/k}p\le n^{1/m}

即

p\le n^{\frac{k-m}{m(k-1)}}

令右式值=C。

那么，我们希望当 p>C 的时候，可以得出 b_1=1 的结论；也即 C^{k+1}>n。

继续列出不等式：

n^{\frac{(k-m)(k+1)}{m(k-1)}}\ge n

得到

(k-m)(k+1)\ge m(k-1)

最终可以得到 k\ge 2m-1，多么简洁美妙的不等式！

比如说，我们希望得到一个 V^{1/3} 的预处理，那么我们就要至少把每个数字分解成 3* 2-1=5 个数字的乘积。

不过一般来说值域都不会很大，所以可能如果是要预处理 10^{18} 的话，就需要达到 V^{1/5}，也就是 9 个数字，这个速度或许会比 \text{bin gcd} 还要慢。。。

不过也是有一定的价值的，至少我估计在 m=3 的时候还是很优秀的。

那么每次计算两个数的 \gcd 都是 O(m) 的。

如果要计算复杂度的话，大概是 O(V^{2/m}+mn^2)，m 是自取的一个数。