我有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
有没有比暴力破解更好的方法?
我有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
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的无效值中,因此这就是我们要寻找的解决方案。
a0
怎么样?看起来是一个常量,从不改变。这是必要的吗? - obratima0
是目前已知的最大的无效值。 - danbanica我可以想到两种不同的解决方案。第一种:
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,因此这比暴力解决方案在渐近意义下更好。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
。s[i]
为零但我们仍然需要超过max(p)的例子? - Miljen Mikicp_max
应该是 lcm(p[i]) - 1,也就是最大可能值(或者解决方案不存在),我已经编辑了我的答案。我现在已经检查了你的解决方案,它真的很优雅 - 给你点赞!请注意,在堆上生成新数字的停止条件也是当你达到 lcm(p[i]) 时,所以不幸的是无论如何都不能避免计算 lcm。 - Miljen Mikic