algorithm - 从 到 坐标的可能路径

Question

我最近接受了一次面试，我的算法只通过了除一个之外的所有测试用例，我不明白为什么。我需要解决的问题是:

给定二维网格中的一个站立点 (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 都是正整数。

Answer 1

GCD(3,7) = GCD(7,3) 但两者都无法从另一个到达。您的条件是必要但不充分的。

请注意，每个点都有一个唯一的可能前导。 IE。对于点 (a,b) 如果 a>b 则前驱是 (a-b,b) 否则前驱是 (a, b-a)。