培玉 · 一试
2026 年江苏预赛
二维整数格的最短非零向量
已知向量
记集合
求集合 中非零向量的模的最小值及所有对应的向量。
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
整数格在这里指两个固定向量的全部整数线性组合。非零行列式保证每个目标坐标有唯一实系数解；逆矩阵分母的整除条件可以检验这组系数是否为整数。
想法从哪来：生成向量的坐标很大，却几乎平行，最短组合可能需要很大的整数系数，盲目枚举系数没有可靠终点。先观察任何整数线性组合都保留哪些同余性质：横坐标的偶性，以及两坐标和的固定整除性，会把候选点压成稀疏格点。 这些条件起初只是必要的；用两个生成向量组成矩阵并求逆，检查满足同余条件的每个整数点能否反解出整数系数，才能把它们当成完整描述。随后不再枚举大系数，而是从原点按模长检查少数小坐标点。找到边界候选后，再写出一个实际整数线性组合，验证下界能取到且所有最短向量都已列全。
直接枚举系数 没有天然边界。先观察两个生成向量的第一坐标都是偶数、 两坐标之和都是 的倍数；再利用行列式为 ，可把这两个同余条件反过来证明为 整个格的精确刻画。最短向量问题于是只需检查原点附近极少的整数点。
解答
设 。因为
所以
反过来，若整数对 满足式 (1)，由
解线性方程
可得
由 ，式 (2) 中 的分子是 的倍数； 的分子既是偶数，又是 的倍数，因此是 的倍数。故 ， 从而式 (1) 恰好刻画了 中的全部向量。
现在若 ，由 为偶数，只可能有 。 当 时，，而 ，所以 ； 当 时，，即 ，均不满足 。因此不存在模小于 的非零向量。
若 ，则 ；结合式 (1)，只能是
并且
所以这两个向量确实都属于 。故所求为
全部对应向量为
复核
将式 (2) 代回两个生成向量可分别得到 ，逆变换无误。 边界 的四个整数点已全部检查，其中恰有两个满足同余条件； 给出的整数线性组合又验证了最小值确实能够取到。
方法总结
二维整数线性组合先形成一个格。与其盲目搜索大系数，不如先从生成向量找必要同余条件， 再用行列式或逆矩阵证明这些条件也充分；格被简化成若干同余类后，最短向量只需按模长 从原点向外检查有限个格点。
为什么评为 F4（会透露解法方向）
从大坐标向量找出X偶数、X+Y为13倍数的隐含格点条件，还要逆解证明充分，再排除短向量并给出达到的整数组合。
已记下，谢谢！