除法的最小公共余数

Question

除法的最小公共余数

5

我有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

有没有比暴力破解更好的方法？

- obratim

1

难道不应该是 0 <= s[i] < p[i] 吗？因为 s[i] = p[i] 相当于 s[i] = 0。 - maraca

作为提醒，PPCG（编程谜题和代码高尔夫）不是SO网站中最简单的网站（与Math.SE和MO不同），它主办编程竞赛。曾经有人提议将该网站更名为编程竞赛和代码高尔夫，但SE并不关心PPCG... - user202729

2个回答

2

我可以想到两种不同的解决方案。第一种：

p_max = lcm (p[0],p[1],...,p[n]) - 1;
for a = 0 to p_max:
    zero_found = false;
    for i = 0 to n:
        if ( s[i] + a ) mod p[i] == 0:
            zero_found = true;
            break;
    if !zero_found:
        return a;
return -1;

我想这就是你所谓的“暴力破解”。请注意，p_max表示p[i]的最小公倍数减1（答案要么在闭区间[0, p_max]中，要么不存在）。该解决方案的时间复杂度在最坏情况下为O(n * p_max)（加上计算lcm的运行时间！）。有一种关于时间复杂度更好的解决方案，但它使用了一个额外的二进制数组 - 经典的时间空间权衡。其思想类似于埃拉托色尼筛法，但是针对余数而不是质数 :)

p_max = lcm (p[0],p[1],...,p[n]) - 1;
int remainders[p_max + 1] = {0};
for i = 0 to n:
    int rem = s[i] - p[i];
    while rem >= -p_max:
        remainders[-rem] = 1;
        rem -= p[i];
for i = 0 to n:
    if !remainders[i]:
         return i;
return -1;

算法解释：首先，我们创建一个名为remainders的数组，它将指示整个集合中是否存在某些负余数。什么是负余数？很简单，注意到6 = 2 mod 4等价于6 = -2 mod 4。如果remainders[i] == 1，这意味着如果我们将i添加到其中一个s[j]中，我们将得到p[j]（即0，这是我们要避免的）。数组填充所有可能的负余数，最多为-p_max。现在我们所要做的就是搜索第一个i，使得remainder[i] == 0并返回它，如果存在的话-请注意，解决方案不一定存在。在问题文本中，您已经表明您正在寻找最小的正整数，我不明白为什么零不能适用（如果所有的s[i]都是正数）。但是，如果这是一个强烈的要求，只需将for循环更改为从1开始而不是0，并增加p_max。此算法的复杂度为n + sum (p_max / p[i]) = n + p_max * sum (1 / p[i])，其中i从0到n。由于所有的p[i]至少为2，因此这比暴力解决方案在渐近意义下更好。

一个更好理解的例子：假设输入是（5,4），（5,1），（2,0）。p_max是lcm(5,5,2) - 1 = 10 - 1 = 9，因此我们创建了一个有10个元素的数组，最初填充为零。现在让我们一对一对地进行：

从第一对中，我们有remainders[1] = 1和remainders[6] = 1
第二对给出remainders[4] = 1和remainders[9] = 1
最后一对给出remainders[0] = 1，remainders[2] = 1，remainders[4] = 1，remainders[6] = 1和remainders[8] = 1。

因此，数组中值为零的第一个索引是3，这是一个期望的解决方案。

- Miljen Mikic

请注意，a 的最小值不一定要低于 max(p) -- 请考虑以下示例：(p, s) = { (2, 1), (5, 1), (5, 3) } -- 在这种情况下，最小有效的 a 值为6。 - danbanica

@qwertyman 在这种情况下，我的算法将输出0作为解决方案，我已经注释了这个特殊情况（在任何模n系统中，0始终被视为常规余数，因此我不明白为什么a应该> 0）。如果a不能是非负的，而是正的，那么你是对的-我们应该扩展max(p)上的循环。是否有一些s[i]为零但我们仍然需要超过max(p)的例子？ - Miljen Mikic

是的，例如如果(p，s)对的集合为{(2,1)，(3,0)，(5,1)，(5,3)}，则从0到7的值都无法使用，a = 8是最小的有效值。 - danbanica

@qwertyman 很好的例子！实际上，p_max 应该是 lcm(p[i]) - 1，也就是最大可能值（或者解决方案不存在），我已经编辑了我的答案。我现在已经检查了你的解决方案，它真的很优雅 - 给你点赞！请注意，在堆上生成新数字的停止条件也是当你达到 lcm(p[i]) 时，所以不幸的是无论如何都不能避免计算 lcm。 - Miljen Mikic

感谢您的赞赏并考虑了我的建议 - 我也点了赞！事实上，在这两种解决方案中都需要最小公倍数。 - danbanica

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- danbanica · Accepted Answer

可以通过比暴力更好的方法来解决问题。暴力的算法复杂度为O(A·n)，其中A是我们要找的最小有效值a。

下面描述的方法使用小根堆，并实现了O(n·log(n) + A·log(n))的时间复杂度。

首先注意到将a替换为(p[i] - s[i]) + k * p[i]的形式，对于第i个对，它会产生余数为零，其中k是正整数。因此，这些数字都是无效的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的无效值中，因此这就是我们要寻找的解决方案。