环线性空间与 Half-GCD

· · 算法·理论

前半部分是好久之前模拟赛时发现的，后半部分是前段时间洗澡时突然就想到怎么做了，全都记录一下。但是其实我是民科，所以所有理论都是我瞎编的。

首先我们熟悉的线性空间是对于一个域 K，定义的向量空间 K^n，因为域能保证对于任意 k,b\in K,\,k\neq 0 均有 kx=b 在 x\in K 上有唯一解，这使得我们的三种基本行变换均有其逆元。

这样确保我们可以把一组向量排成矩阵，并任意地做线性变换而不改变其张成的线性空间。

那考虑对于一个环 R 呢？最常见的问题就是在整数一维空间上 \mathbb{Z} 上，我们有熟知结论，一个含有非 0 元素的集合 S 张成的整数线性空间是 \{kd\mid k\in\mathbb{Z}\}，其中 d=\operatorname{gcd}(S)，这是由于三种基本行变换中其实只有把某一行自由放缩为其 k 倍（k\neq 0）是不一定有逆的（只在 k=\pm 1 时）有，这就让我们想起了辗转相减，做一下就可以得到这个结果（这也另一面说明作为辗转相减的加速版本辗转相除，虽然名字中有「除」但实则也是线性变换）。

这就启示我们可以推广到 \mathbb{Z}^n，只要把高斯消元时计算两行第 i 列系数的比值再乘这个系数相减的步骤改为依第 i 列系数做辗转相减。当然此时我们不好分析复杂度，因为系数在运算的过程中会变得很大，但是对于 \mathbb{Z}_m^n 就可以用经典均摊分析分析到 \mathcal{O}(n^2\lvert S\rvert+n\operatorname{rank}(S)\log m) 次运算。

当然这就告诉我们对于一般的环 R，只要我能做一维的情况（例如找到一个整数组合量 f，最小值取在 f(0)，且对于任意两个非零元 a,b\in R，可以找到某个系数 k\in R 使得 f(a+kb)<f(a) 或 f(ka+b)<f(b)，就可以做辗转相除），就可以通过把描述这个过程的矩阵记录下来作用在整行上，用类似高斯消元的过程在有限时间内把线性空间表示成若干个有不同主元的向量张成的（当然这也就是一组基向量）。

对于一个域 K，记 K(x) 为系数为 K 的一元整式集合（显然对于 (K(x),+,\cdot,0,1) 是一个环），定义 K(x) 上的等价关系 \propto 为 f(x)\propto g(x) 当且仅当存在非零系数 k\in K 使得 kf(x)=g(x)。容易验证这确实构成一个等价关系。

对于一个含非常数的集合 S\subseteq K(x)，仿照 \mathbb{Z}，定义 \operatorname{gcd}(S) 为其张成的空间上次数最小的一项，当然这会有多解，但是可以发现解集恰好构成一个等价类。当然我们也同样能说明张成的空间恰好是这个 \gcd 的所有倍数。

另一个角度，用整式的唯一分解定理也可以说明这等同于一元情况下我们熟知的逐个既约式的幂次取 \min 的定义式，当然这不在我们这次主题的考察范围内。

问题：

给定两个次数小于 n 且不全为常数的一元整式 f(x),g(x)，求 \operatorname{gcd}\left\{f(x),g(x)\right\}。

我们当然可以做辗转相除法，这里选取的组合量就是次数，因为我们知道对于 f(x),g(x)\in K(x) 且 g(x) 不是常数，可以定义 g(x)\bmod f(x) 满足其次数小于 f(x)。

但很遗憾这样每次最坏只能将次数减少 1，可以发现我们的总复杂度变为了 T(n)=T(n-1)+\Theta(M(n))=\Theta(M(n)n)。

我们考虑这样一件事，我们的瓶颈主要在于太多太多次高项数的除法，以及为了能计算下一次除法而进行的乘法和加法。但是可以发现例如计算 (202x^{726}+107)\div(526x^{502}+1020) 时其实和低次项几乎没什么关系，不如把这些变换系数都囤到后面一起做。

那我们先对前 t 位消，记录出操作矩阵，消出来后对低位也变换一下，此时小的那个已经变成次数小于 n-t 的了，将另一个对其取模就缩到了 n-t 规模的问题了吧？取 t\approx\frac{n}{2} 最优可以得到 T(n)=T(\frac{n}{2})+\Theta(M(n))=\Theta(M(n))，就这样做完了吗？

其实根本不对，那个矩阵系数是一元整式，最大次数可达 t-1，足以让低位污染到高位（而且事实上只要次数 \geq 1 就有机会污染到）。

那我们只能放松一下目标，既然高位的低位必然会被低位污染到，那我们不如放飞自我，也只消去高 \frac{n}{2} 位，这样矩阵系数次数不超过 \frac{n}{2}，对于规模为 n 的问题，按照 \frac{n}{4} 分段我们先对 \frac{n}{2} 消一下高 \frac{n}{4} 位（即第一段），低位污染只会污染到第二段就也无所谓，然后再对第二段和第三段放一起跑一下消掉第二段，操作代入到第四段污染也只会污染到第三段，这样就消掉了高 \frac{n}{2} 位，当然前面说次数和位数时我们忽略了一些加性常数，但是你只需要执行常数轮辗转相除就可以去掉这些额外的常数次了，于是我们可以分析出这部分复杂度是 T(n)=2T(\frac{n}{2})+\Theta(M(n))=\Theta(M(n)\log n)。

有了这个工具再来解决原问题，每次用 \mathcal{O}(M(n)\log n) 的时间消掉高 \frac{n}{2} 位，可以得到 T(n)=T(\frac{n}{2})+\Theta(M(n)\log n)=\Theta(M(n)\log n)。