algorithm - 除法的最小公余数

Question

我有 n 对数字:( p[1], s[1] ), ( p[2], s[2] ), ... , ( p[n] , s[n] )

其中p[i]为大于1的整数； s[i] 是整数:0 <= s[i] < p[i]

有什么方法可以确定最小正整数 a ，这样对于每一对:

( s[i] + a ) mod p[i] != 0

还有比蛮力更好的方法吗？

Answer 1

有可能比蛮力做得更好。蛮力将是 O(A·n)，其中 A 是我们正在寻找的 a 的最小有效值。

下面描述的方法使用 min-heap并达到O(n·log(n) + A·log(n))的时间复杂度。

首先，请注意用 (p[i] - s[i]) + k * p[i] 形式的值替换 a 会导致 a对于任何正整数 k，第 i^th 对中的 reminder 等于零。因此，该表单的数字是无效的 a 值(我们正在寻找的解决方案不同于所有这些值)。

所提出的算法是一种生成该形式的数字的有效方法(对于所有 i 和 k)，即无效值对于 a，按递增顺序。一旦当前值与前一个值相差超过 1，就意味着中间有一个有效的 a。

下面的伪代码详细介绍了这种方法。

1. construct a min-heap from all the following pairs (p[i] - s[i], p[i]), 
    where the heap comparator is based on the first element of the pairs.
2. a0 = -1; maxA = lcm(p[i])
3. Repeat
     3a. Retrieve and remove the root of the heap, (a, p[i]).
     3b. If a - a0 > 1 then the result is a0 + 1. Exit.
     3c. if a is at least maxA, then no solution exists. Exit.
     3d. Insert into the heap the value (a + p[i], p[i]).
     3e. a0 = a

备注:这样的a有可能不存在。如果在 LCM(p[1], p[2], ... p[n]) 下找不到有效的 a，则可以保证没有有效的 a 存在。

---

我将在下面展示该算法如何工作的示例。

考虑以下 (p, s) 对:{ (2, 1), (5, 3) }。

第一对表明 a 应该避免像 1, 3, 5, 7, ... 这样的值，而第二对表明我们应该避免像这样的值2、7、12、17，...。

最小堆最初包含每个序列的第一个元素(伪代码的第 1 步)——下面以粗体显示:

• 1, 3, 5, 7, ...

• 2, 7, 12, 17, ...

我们检索并移除堆头，即，两个粗体中的最小值，这是1。我们将该序列中的下一个元素添加到堆中，因此堆现在包含元素 2 和 3:

• 1, 3, 5, 7, ...

• 2, 7, 12, 17, ...

我们再次获取堆头，这次它包含值 2，并将该序列的下一个元素添加到堆中:

• 1, 3, 5, 7, ...

• 2, 7, 12, 17, ...

算法继续，接下来我们将检索值3，并将5添加到堆中:

• 1、3、5、7、...

• 2, 7, 12, 17, ...

最后，现在我们检索值 5。此时我们意识到值 4 不在 a 的无效值中，因此这就是我们正在寻找的解决方案。