我最近接受了一次采访，我的算法只通过了除一个以外的所有测试用例，我无法弄清楚为什么。我需要解决的问题是：
给定2D网格中的站点（a，b）是否可以到达目的地点（x，y）。他唯一能做的就是从某个点（a，b）移动到（a + b，b）或（a，a + b）点。
我试图用gcd来解决它。例如如果gcd（a，b）= gcd（x，y）那么其他可能就没有了。直觉是如果k是a＆b的gcd。那么，k也会除（a + b）。我使用以下算法来计算gcd：
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
编辑：数字a，b，x和y都是正整数。
您现在在帖子上有两个问题：
Photon的link涵盖了这一点。GCD是必要但不充分的条件。
是的，如果a = b，那么如果GCD（x，y）= a = b，则可以得到（x，y）。但是，这并不能概括为所有问题对。平凡的反例试图从（N，1）到达（1，N），其中N> 1。另一个是（2,3）=>（4,5）。
所以，让我们进入定性部分：“我无法弄明白......”。我怀疑问题是你看到Euclid算法和你的加法步骤之间的相似性。更强大的是，链接中的“向后”算法表明Euclid的算法适用。
它可以在某种程度上，但不像你试图使用它那样简单和普遍。将该问题视为笛卡尔平面中正整数格的图。允许的操作（有向边）定义了如何从一个点移动到另一个点。
这里的关键术语是指向的：一旦你从一个起点“移动”到一个定义你系统中GCD的那个，你就没有自由回溯这些步骤了。您可以向前或向后移动图表空间。
例如，虽然您的向后过渡允许您从（4,1）移动到（1,1）或从（1,4）移动到（1,1），但您不能使用它来从（4,1）结束路径）至（1,4）：这些动作的一半是不允许的方向。
这有助于消除混乱吗？
GCD（3,7）= GCD（7,3），但两者都无法到达。你的病情是必要的，但还不够。
请注意，每个点都有一个独特的可能前身。即对于点（a，b），如果a> b，那么前一个是（a-b，b），否则前一个是（a，b-a）。