arrays - 求另外两个数与第三个数的加减运算可组成的数组元素个数

Question

给定三个数字 d、a、b 和一个整数数组。我们可以对 d 添加/减去 a 或 b 任意次数。我们应该找到数组中数字的计数，该数组可以通过将这些操作应用于 d 而形成。

示例:如果数组为 [14, 15, 63] 且 d = 4，则 a = 7 且 b = 9;

那么输出应该是2。作为14 = 4 + (9 - 7) + (9 - 7) + (9 - 7) + (9 - 7) + (9 - 7)
63 = 4 + 9 + 9 + 9 + 9 + 9 + 7 + 7但是15不能用任何组合得到。因此输出为 2。

请建议一个计算这个的算法。提前致谢。

Answer 1

只是为@user3386109 的评论添加更多细节，

Given three numbers d, a, b and an array of integers. We can add/subtract a or b to d any number of times. We are supposed to find the count of numbers in the array which can be formed by applying these operations to d.

设数组中的一个元素为x，

现在，假设 x = d + a*i + b*j，其中 i 和 j 是任意整数。如果这需要成立，则 x - d = a*i + b*j。让我们看看右边的术语是怎么说的，

来自 Bézout's identity

Bézout's identity — Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

我们看到 a*i + b*j 恰好是 GCD(a,b) 的倍数。所以差异 x-d 必须被 GCD(a,b) 整除，就像 @AshutoshTiwari 指出的那样。