自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:48:50，当前版本为作者最后更新于2022-02-03 13:21:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

• Update on 2022.11.30：修改笔误。
• Update on 2025.1.22：修订。

*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, c$。
• 倍乘：对应本题即乘以任意非 $0$ 整数。
• 倍加：对应本题即向量加上任意整数倍其它向量。

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

• 交换显然不改变张成。
• 倍乘变换 可能改变 张成，因为整数乘法不可逆。如 $\mathrm{span}\{(0, 1), (1, 0)\}$ 显然不等于 $\mathrm{span}\{(0, 2), (1, 0)\}$。
• 倍加变换 不改变 张成。对任意 $p = y(a + xb) + zb\in \mathrm{span}(a + xb, b)$，它仍是 $a, b$ 的整系数线性组合 $ya + (xy + z)b$。对任意 $p = ya + zb \in \mathrm{span}(a, b)$，我们也总可以将其表示为 $a + xb$ 和 $b$ 的整系数线性组合 $y(a + xb) + (z - xy) b$。

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

具体地，考虑两个向量 $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;
}