P4356 [CERC2015]Looping Labyrinth 题解

Linshey · 2022-03-10 09:48:48 · 题解

假设不把它复制无限遍，而是看做是一个上下连通且左右连通地图，进行一次 dfs 的预处理后，就变成了下面这样一个问题：

判断方程 \sum x \vec{v_i}=\vec{y} 是否整数解（其中 v 和 y 是给定的二维向量）。

分两种情况讨论：

1. 所有向量都在 x 轴和 y 轴上，显然对两维坐标分别用裴蜀定理判断就行。
2. 否则，我们取一个 x 并消掉它，那么就只剩一维了，也是用裴蜀定理判断就行了。

感谢 @18Michael