网格路径最大公约数 题解

思路

答案一定同时整除左上角和右下角。枚举这两个端点最大公约数的因子，并判断是否存在一条全部能被该因子整除的单调路径。

做法

子任务 1：枚举路径

DFS 枚举所有向右、向下路径，沿途维护最大公约数并取最大值。

子任务 2：二值网格

答案只可能是 1 或 2。只需判断值为 2 的格子能否组成从左上到右下的单调路径。

子任务 3：因子枚举

令 $g=\gcd(a_{1,1},a_{n,m})$。按从大到小枚举 $g$ 的所有因子 $d$，对能被 $d$ 整除的格子做布尔可达性 DP。第一个可达的 $d$ 即为答案。

正确性证明

引理 1 任意路径的最大公约数都是 $g$ 的因子。

证明 路径包含两个端点，所以其最大公约数同时整除两个端点，必整除 $g$。∎

引理 2 因子 $d$ 可作为某条路径最大公约数的约数，当且仅当存在一条所有格子均能被 $d$ 整除的单调路径。

证明 路径最大公约数能被 $d$ 整除等价于路径每个数都能被 $d$ 整除；布尔 DP 恰好枚举所有单调路径。∎

定理 算法输出最大可能路径最大公约数。

证明 由引理 1，最优答案在枚举集合中；由引理 2，每次可达性判断正确。按降序返回首个可达因子，故其最大。∎

复杂度

设 $\tau(g)$ 为 $g$ 的因子数，满分算法每组时间复杂度 $O(nm\tau(g)+\sqrt g)$，空间复杂度 $O(nm)$。