给定范围内的总和和乘积

Question

给出四个正整数 , , 和 ,有没有办法快速找到任何两个整数 和 这样:

• ,和
• ？

什么时候 和 ,有一个封闭的形式 使用二次方程解决这个问题.我们只需找到根源 它会给我们一个合适的 .

什么时候 ,我知道如何解决它 通过注意到曲线 是凸的,所以我们可以二元搜索一个合适的 .

什么时候 ,它可以解决 通过保理 并寻找一对总和到该范围内的值的因子.

然而,当它们都是范围时,我想不出任何可以有效解决这个问题的算法.有一些可能的启发式方法,比如修复两个中的一个(迭代较小的范围等),或立即报告当可以用两个整数求和的最大可能产品时不存在对 小于 等

不幸的是,我无法想出任何能够在一般情况下工作的东西,而不是迭代任何一件事 要么 (可能有一些额外的小因素).是否有一个很好的算法,或一些花哨的数学,提供更快的解决方案？

或者,有没有办法证明迭代很快终止？(在处理了一些角落案件等之后)我对有效对的数量不感兴趣; 找到任何一对都会.如果允许总和的范围足够大,似乎迭代产品并试图找到相应的和趋向于快速找到解决方案.可以有某种证据吗？

我非常感谢任何帮助!

Answer 1

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

1. 求这些总和：small_sum = i +上限(P1/i)和big_sum = i+floor(P2/i)，其中i在1和sqrt(P2)之间。

2. 如果small_sum > big_sum 或big_sum < s1 或small_sum > s2 则i 不是解的一部分。继续前行。

3. 否则，max(small_sum, s1) min(big_sum, s2) 以及“好总和”之间的所有值。对于其中任何一个，令 j = good_sum - i。那么i+j是s1和s2之间的值，i*j是p1和p2之间的值。

我们最多检查 i 的 sqrt(P2) 值，并且对于每个值我们都在不断地工作。

编辑——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