P16343 [科大国创杯初中组 2026] 行走

Subtask 0 为民间数据，Subtask 1 为官方测试数据。

小可可有一个 $n \times n$ 的方格，方格 $(i, j)$ 上有一个正整数 $a_{i,j}$。小可可希望从 $(1, 1)$ 走到 $(n, n)$，他只能往下或往右走，即从 $(i, j)$ 走到 $(i+1, j)$ 或从 $(i, j)$ 走到 $(i, j+1)$。他身上有一个正整数 $v$，初始为 $a_{1,1}$，小可可每走到一个格子 $(i, j)$，$v$ 会变为 $\gcd(v, a_{i,j})$。小可可想知道他走到 $(n, n)$ 时 $v$ 最大为多少。 > $\gcd(i, j)$ 表示正整数 $i$ 和 $j$ 的最大公约数，即为最大的正整数 $d$ 满足 $d$ 整除 $i$ 并且 $d$ 整除 $j$。

输入共 $n+1$ 行。 - 第一行两个正整数 $n, V$。 - 第 $2$ 到 $n+1$ 行每行 $n$ 个正整数，第 $i+1$ 行第 $j$ 个数表示 $a_{i,j}$。

输出一行一个正整数表示答案。

#### ****样例解释**** 小可可的最优方案为 $(1, 1) \to (2, 1) \to (2, 2)$。 #### ****其它样例说明**** * **样例 2 ~ 5**：见选手目录下的 `walk/walk*.in` 与 `walk/walk*.ans`。 #### ****数据范围**** 对于所有数据，保证 - $1 \le n \le 1000$, - $1 \le a_{i,j} \le V \le 10000$ - 所有输入数字都是正整数。 | 测试点编号 | $n \le$ | $a_{i,j}, V \le$ | 特殊性质 | | :---: | :---: | :---: | :---: | | $1, 2, 3$ | $10$ | $10000$ | 无 | | $4, 5, 6$ | $100$ | $100$ | 无 | | $7, 8$ | $1000$ | $10000$ | 保证数据随机 | | $9, 10$ | $1000$ | $10000$ | 无 |