O(v) - O(1) GCD
Purslane
·
·
题解
Solution
感觉我的科技树还是不够茂盛，最近多学点数学的科技。
如果我们求最大公约数的两数都在值域 [1,V] 内，我们需要在 O(V) 的时间内预处理出 \forall x_1 , x_2 \le \sqrt V 的 \gcd(x_1,x_2) 和另外一个东西，然后查询只需要 O(1) 的时间。
Lemma
任意一个数 n，都可以写成 a \times b \times c 的形式，其中 a \le b \le c 且 c \le \sqrt n 或 c 是个质数。
证明：归纳的，我们尝试用 n 的因子的合法解构造 n 的合法解。当 n 是个质数（或者 1）的时候，解 (1,1,n) 一定是合法的。
不然假设 n 的最小质因子为 p，假设 \frac{n}{p} 的解为 \{a,b,c\}(a \le b \le c)。
我们证明：将 ap，b，c 从小到大排序后任然是合法的解。其实也就只需要证明 ap \le \sqrt n。
如果 c \ge \sqrt{\frac{n}{p}}，它是个质数，那么一定有 a < \sqrt[4]{\frac{n}{p}}。再乘上 p，要它不大于 \sqrt n 的等价条件是 p^3 \le n。
不然就有 a \le \sqrt[3]{\frac{n}{p}}，要乘上 p 之后不大于 \sqrt n 的等价条件是 p^4 \le n。
我们可以感性理解，若 n 有不少于 4 个质因子（相同的算一个），这两个条件肯定都成立。
假设 n 有 3 个质因子，也就是说 \frac{n}{p} 只有两个，我们记为 p_1 和 p_2。那么实际上 \frac{n}{p} 只有唯一的解：\{1,p_1,p_2\}。那么 \{p,p_1,p_2\} 无论如何都是 n 正确的解。
如果 n 有两个质因子，也就是 \frac{n}{p} 是个质数。那么 \{1,p,\frac{n}{p} \} 也是合法的解。
这样我们不仅证明了这样的拆分是存在的，还给出了一种用线性筛可以在 O(V) 复杂度内构造解的方法。
好的，如果我们要求 x 和 y 的最大公约数，我们用上面的方法把 x 拆成了 a \times b \times c。我们求出 \gcd(a,y)，然后让 y 除以这个数（防重复），然后处理 b 和 c。
这里的 \gcd 求起来就相当高效。当 a 是质数，直接返回 y 是不是 a 的倍数。否则先辗转相除一次变成 \gcd(a,y \bmod a)，然后转化为两个在 \sqrt n 之内数的最大公约数，这是我们已经预处理过了的。