给定范围内的求和与乘积

Question

给定范围内的求和与乘积

algorithmmath

7

给定四个正整数, , 和，是否有一种快速找到任意两个整数和的方法，使得：

$S_1 \leq a+b \leq S_2$ ，和
$P_1 \leq ab \leq P_2$ ？

当

和

时，使用二次方程式可以得到一个闭合形式的

解决方案。我们只需找到

的根，就能得到一个适当的

。

当时，我知道如何通过注意到曲线是凸的，所以我们可以二分搜索适当的，从而在中解决它。

当

时，可以通过对

进行因式分解，并查找在范围内求和的一对因子来解决

。请注意保留HTML标记。

然而，当两个都是范围时，我想不出任何可以高效解决此问题的算法。有一些可能的启发式方法，比如固定其中一个（遍历较小的范围等），或者在两个整数之和为时可以制造的最大可能乘积小于时立即报告不存在任何一对等。

很遗憾，我还没有想出任何比迭代或（可能带有一些额外的小因子）更快的通用解决方案。是否有一种好的算法或一些花哨的数学方法可以提供更快的解决方案？

另外，是否有一种方法可以证明迭代会迅速终止？（在处理一些边缘情况等之后。）我不关心有效对数的数量；找到任何一对即可。如果允许的总和范围足够大，则迭代乘积并尝试找到相应的总和似乎很快就能找到解决方案。这是否可能有某种证明呢？

我非常感谢任何帮助！

- Robin Yu

S1、S2、P1和P2的范围有限制吗？例如，如果它们都是严格正数，那么解决起来应该比一般情况更容易，因为例如a和b都不能大于或等于S2或P2。因此，搜索范围限制为1..min(S2, P2)。 - twalberg

是的，它们保证是正数；我认为即使这个版本也足够困难。我已经更新了问题；感谢您的澄清！ - Robin Yu

只是一个观察，但是 max(S1 - b, P1/b) <= a <= min(S2 - b, P2/b)。也许描述这个不等式可以帮助找到 O(1) 的解决方案。 - darksky

1个回答

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

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

- Dave · Accepted Answer

您可以在O(sqrt(P2))时间内解决它。

1. 找到这些总和：small_sum = i + ceiling(P1/i)和big_sum = i + floor(P2/i)，其中i在1到sqrt(P2)之间。 2. 如果small_sum > big_sum或big_sum < s1或small_sum > s2，则i不是解的一部分。继续下一个i。 3. 否则，max(small_sum, s1) min(big_sum, s2)，以及所有“好总和”之间的值。对于其中任何一个，让j = good_sum - i。然后i + j是s1和s2之间的值，而i * j是p1和p2之间的值。我们检查最多sqrt(P2)个i值，并且对于每个这些值，我们都会进行恒定的工作。

编辑 - Ruby实现

def solve(s1, s2, p1, p2)
  max_i = (p2**0.5).floor
  1.upto(max_i) do |i|
    small_sum = i + (p1/i.to_f).ceil
    big_sum = i + (p2/i.to_f).floor
    next if big_sum < s1 || small_sum > s2 || big_sum < small_sum
    good_sum = [small_sum, s1].max
    puts "sum: #{i} + #{good_sum - i} = #{good_sum}, #{s1} <= #{good_sum} <= #{s2}"
    puts "product: #{i} * #{good_sum-i} = #{i*(good_sum-i)}, #{p1} <= #{i*(good_sum-i)} <= #{p2}"
    return
  end
  puts "no solution"
end