我有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
还有比蛮力更好的东西？
有可能比蛮力做得更好。暴力破解的结果是O (A\xc2\xb7n)，其中 A 是我们正在寻找的a的最小有效值。
\n\n下面描述的方法使用最小堆并实现O (n\xc2\xb7log(n) + A\xc2\xb7log(n)) 时间复杂度。
\n\n首先，请注意，对于任何正整数k ，将a替换为 (p[i] - s[i]) + k * p[i]形式的值会导致第i 对中的提示等于零。因此，该形式的数字是无效的值（我们正在寻找的解决方案与所有这些数字都不同）。
\n\n所提出的算法是一种以递增顺序生成该形式的数字（对于所有i和k）的有效方法，即a的无效值。一旦当前值与前一个值相差超过 1，就意味着存在有效的中间值。
\n\n下面的伪代码详细介绍了这种方法。
\n\n1. construct a min-heap from all the following pairs (p[i] - s[i], p[i]), \n where the heap comparator is based on the first element of the pairs.\n2. a0 = -1; maxA = lcm(p[i])\n3. Repeat\n 3a. Retrieve and remove the root of the heap, (a, p[i]).\n 3b. If a - a0 > 1 then the result is a0 + 1. Exit.\n 3c. if a is at least maxA, then no solution exists. Exit.\n 3d. Insert into the heap the value (a + p[i], p[i]).\n 3e. a0 = a\n备注：这样的a可能不存在。如果在 LCM(p[1], p[2], ... p[n]) 下找不到有效的a ，则保证不存在有效的a。
\n\n我将在下面展示该算法如何工作的示例。
\n\n考虑以下 (p, s) 对：{ (2, 1), (5, 3) }。
\n\n第一对表示a应避免使用1, 3, 5, 7, ...等值，而第二对表示我们应避免使用2, 7, 12, 17, ...等值。
\n\n最小堆最初包含每个序列的第一个元素（伪代码的步骤 1）——下面以粗体显示：
\n\n1、3、5、7、...
2、7、12、17、...
我们检索并删除堆头，即两个粗体中的最小值，这是1。我们将该序列中的下一个元素添加到堆中，因此堆现在包含元素 2 和 3：
\n\n1, 3 , 5, 7, ...
2、7、12、17、...
我们再次检索堆头，这次它包含值2，并将该序列的下一个元素添加到堆中：
\n\n1, 3 , 5, 7, ...
2, 7 , 12, 17, ...
算法继续，我们接下来将检索值3，并将 5 添加到堆中：
\n\n1, 3, 5 , 7, ...
2, 7 , 12, 17, ...
最后，现在我们检索值5。此时我们意识到值4不属于a的无效值，因此这就是我们正在寻找的解决方案。
\n