algorithm - 计算两位数的可能性

Question

有两个变量:a 和 b。 a的初值为1，b为0。有两个按钮:红色和蓝色。红色按钮将 b 的值添加到 a，蓝色按钮将 a 的值添加到 b。

red : a = a+b 
blue: b = b+a

现在的问题是你是否可以在 a 上得到 int X，在 b 上得到 Y。

例如，给定X = 7, Y=9。

你从 a=1, b=0 开始。蓝色按钮两次将使 b 0+1+1=2，而 a 保持不变。然后红色按钮可以按3次，1+2+2+2=7。所以a=7，b=2，那么蓝色按钮可以让b 2+7=9。最后，a=7 和 b=9。

我如何计算使用这两个按钮获得 X 和 Y 的可能性？该算法必须适用于更大的数字 (>1000)

您不必知道按钮的路径即可获取数字，而只需知道可能性即可。

Answer 1

一对(X, Y)是可能的，如果X是正数，并且X和Y的最大公约数 是 1。这相对容易证明:

First note, that if X,Y is possible, then the gcd must be 1. Because otherwise, consider a minimal X,Y that's possible with gcd not equal to 1. Neither X nor Y can be 0. But this minimal X,Y must have come from a possible X-Y,Y or X,Y-X, but both of these have the same gcd as X,Y, and are smaller, contradicting our assumption of minimality.

Second, suppose there's X,Y has gcd equal to 1 (other than 0,1 which is the only pair with gcd=1 and X=0) which is not possible. Consider a minimal such X,Y. Then again, this must have come from either X-Y,Y or X,Y-X which both have gcd=1, and again we've got a contradiction from the assumption of minimality.

Thus we've shown that except for 0,1, then gcd(X,Y)=1 if and only if X,Y is reachable.

然后可以使用标准的 gcd 算法来计算答案:

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def solvxy(X, Y):
    return X>0 and gcd(X, Y)==1