CF1375I Cubic Lattice

在三维欧几里得空间中，立方格点 $L$ 是由以下方式定义的一组点： $$L=\{u \cdot \vec r_1 + v \cdot \vec r_2 + w \cdot \vec r_3\}_{u, v, w \in \mathbb Z}$$ 其中 $ \vec r_1, \vec r_2, \vec r_3 \in \mathbb{Z}^3 $ 是三个整数向量，满足以下条件： * $ \vec r_1 $、$ \vec r_2 $ 和 $ \vec r_3 $ 两两正交： $$ \vec r_1 \cdot \vec r_2 = \vec r_1 \cdot \vec r_3 = \vec r_2 \cdot \vec r_3 = 0 $$ 其中 $ \vec a \cdot \vec b $ 表示向量 $ \vec a $ 和 $ \vec b $ 的点积。 * $ \vec r_1 $、$ \vec r_2 $ 和 $ \vec r_3 $ 的长度都相等： $$ |\vec r_1| = |\vec r_2| = |\vec r_3| = r $$ 给定一组整数点 $A=\{\vec a_1, \vec a_2, \dots, \vec a_n\}$，第 $i$ 个点的坐标为 $a_i=(x_i;y_i;z_i)$。令 $g_i=\gcd(x_i,y_i,z_i)$。保证 $ \gcd(g_1,g_2,\dots,g_n)=1 $。 你需要找到一个立方格点 $L$，使得 $A \subset L$，并且 $r$ 尽可能大。

第一行包含一个整数 $n$（$1 \leq n \leq 10^4$），表示点集 $A$ 的点数。 接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i$、$y_i$、$z_i$（$0 < x_i^2 + y_i^2 + z_i^2 \leq 10^{16}$），表示第 $i$ 个点的坐标。 保证 $ \gcd(g_1,g_2,\dots,g_n)=1 $，其中 $g_i=\gcd(x_i,y_i,z_i)$。

第一行输出一个整数 $r^2$，即最大可能的 $r$ 的平方。 接下来的 $3$ 行，每行输出一个向量 $ \vec r_1 $、$ \vec r_2 $ 和 $ \vec r_3 $ 的坐标。 如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译