P3421 [POI2005]SKO-Knights

· · 题解

*P3421 [POI2005] SKO-Knights

题目要求我们找到两个向量 d, e，使得它们的 整系数 线性组合得到的线性空间（张成）等于给出的所有向量的整系数张成。

记 \mathrm{span}(S) 表示集合 S 的整系数张成，即

\mathrm{span}(S) = \left\{\sum\limits_{a_i\in S} c_ia_i :c_i\in \mathbb{Z}\right\}

Sol 1

如果我们能将三个向量 a, b, c 合并成等价的两个向量 d, e，就能解决本题。根据基础的线性代数知识，不改变张成的初等行变换有三种：

当然，上述性质仅在 实系数 线性组合的前提下成立。当要求系数为 整数 时：

很好！如果整系数倍加变换不改变整系数张成，就可以使用 辗转相减法。

具体地，考虑两个向量 a, b，我们能够在不改变其整系数张成的前提下，将 b 的某一维变为 0。只需对 a, b 在这一维进行辗转相减法即可。

考虑三个向量 a, b, c，我们对 a, b 在 x 这一维进行辗转相减，再对 a, c 在 x 这一维进行辗转相减。此时 x_b, x_c 均为 0，意味着 b, c 共线。因此，对 b, c 在 y 这一维进行辗转相减，即 y_b\gets \mathrm{gcd}(y_b, y_c)，此时 c 变成零向量，对 \mathrm{span}(a, b, c) 没有贡献，可以直接舍去，即此时 \mathrm{span}(a, b, c) = \mathrm{span}(a, b)。

综上，我们在 \mathcal{O}(n\log V) 的时间内解决了问题，其中 V 是值域。

注意题目限制坐标绝对值不超过 10 ^ 4。辗转相减法得到最终的 a 时，x_a 和 y_b 是原坐标的 \gcd，显然满足坐标限制。但 y_a 不一定，因此要对 y_b 取模，相当于做了一步辗转相减（此时 x_b = 0 所以不需要改变 x_a）。最终得到的坐标绝对值不超过 10 ^ 2，比题目限制优一个数量级。

从上述过程中，我们发现一个有趣的性质：整系数意义下，两个向量可以在不改变其张成的前提下，使其中一个向量的某一维变成 0，而另一个向量的对应维变成原来两个向量在这一维上的 \gcd。这也是解决本题的关键性质。

Sol 2

让我们深入地钻研一下题解区的其它做法。

实际上两者的核心思想是等价的：将两个向量的其中一个的某一维变成 0，另一个的对应维变成 \gcd。不同点在于，线性代数做法是从倍加变换和辗转相除法推得该性质，即我们使用正确性有保证的方法，最终得到的结果是这样的性质。而题解区的做法是首先令这一条件成立，再根据得到的线性方程组，使用 exgcd 和一些数学推导求解。这体现了 exgcd 与辗转相除的本质联系。

不妨设对于向量 a, b，我们要将 x_b 变为 0。则 x_{a'} 只能等于 d_x = \gcd(x_a, x_b)（不管 y 坐标，由裴蜀定理，能达到的 x 坐标恰为 d_x 的所有倍数）。因此，对于方程 x_ax + x_by = d_x，使用 扩展欧几里得 算法求得一组特解 (x_0, y_0)，则 y_{a'} = y_ax_0 + y_by_0，因为 a' = x_0a + y_0b。

对于 b'，观察到 a' 的通解为 (x_0 + k\frac {x_b} {d_x}, y_0 - k\frac {x_a} {d_x})，所以保持 x_{a'} = d_x 不变，y_{a'} 的最小变化量为 \frac {y_a x_b} {d_x} - \frac {y_b x_a}{d_x}，即让 k 加 1 对 y_{a'} 产生的变化量。因为 x_{b'} = 0，所以 y_{b'} 只能等于这个最小变化量。可以验证这样得到的 a', b' 符合要求。

综上，我们将 a, b 写成了 a', b'，其中 x_{a'} = \gcd(x_a, x_b)，y_{a'} 用 exgcd 求解，x_{b'} = 0，y_{b'} = \frac{y_ax_b - x_ay_b}{\gcd(x_a, x_b)}。对 a, c 的 y 坐标做类似的操作，再合并 b, c 即可。

Sol 3

另一种求解 y_{b'} 的思路（来源 TheLostWeak 的博客）：a', b' 可以整系数线性组合出 a, b。

考虑 a'。因为 x_{a'} = \gcd(x_a, x_b)，所以为了使横坐标等于 x_a，需要将 a' 乘以 \frac{x_a}{\gcd(x_a, x_b)} 即 \frac{x_a}{x_{a'}} 的系数，得到 (x_a, \frac{x_ay_{a'}}{x_{a'}})。因为可以通过向量 b' = (0, y_{b'}) 得到 (x_a, y_a)，因此 y_{b'} \mid \ y_a - \frac{x_ay_{a'}}{x_{a'}} 。同理 y_{b'} \mid \ y_b - \frac{x_by_{a'}}{x_{a'}}。因此

y_{b'} = \frac {\gcd(y_ax_{a'} - x_a y_{a'}, y_bx_{a'} - x_by_{a'})} {x_{a'}}

若 y_{b'} 小于上述 \gcd，将导致存在 p\in \mathrm{span}(a', b')，p\notin \mathrm{span}(a, b)。若 y_{b'} 大于上述 \gcd，a', b' 无法整系数线性组合出 a, b 中的至少一个。

抛砖引玉：联立后两种方法描述 y_{b'} 的式子，稍作化简后得到等式

y_ax_b - x_ay_b = \gcd(y_ax_{a'} - x_a y_{a'}, {y_bx_{a'} - x_by_{a'}})

下方是线性代数辗转相除法的代码，非常容易理解。

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 5;
int n, a[N], b[N];
int main() {
    cin >> n >> a[1] >> b[1];
    for(int i = 2; i <= n; i++) {
        cin >> a[i] >> b[i];
        while(a[i]) {
            if(abs(a[1]) < abs(a[i])) swap(a[1], a[i]), swap(b[1], b[i]);
            else b[1] -= b[i] * (a[1] / a[i]), a[1] %= a[i];
        } if(i > 2) b[2] = __gcd(b[2], b[i]), b[1] %= b[2];
    } cout << a[1] << " " << b[1] << endl << a[2] << " " << b[2] << endl;
    return 0;
}