我想找到满足某些条件C（m）的最大值m = a * b
1 <= a <= b <= 1,000,000.
为了做到这一点，我想以a * b的降序迭代所有对a，b。
例如，对于最大为5的值，顺序为：
5 x 5 = 25
4 x 5 = 20
4 x 4 = 16
3 x 5 = 15
3 x 4 = 12
2 x 5 = 10
3 x 3 = 9
2 x 4 = 8
2 x 3 = 6
1 x 5 = 5
1 x 4 = 4
2 x 2 = 4
1 x 3 = 3
1 x 2 = 2
1 x 1 = 1
到目前为止，我已经提出了一种类似于BFS的树搜索方法，在该方法中，我从当前“已访问”的集合中生成候选者，并选择最高价值的候选者，但这是一团糟，我不确定正确性。我想知道我是否缺少某种技巧。
如果存在这样的单调函数f（a，b），我也对更一般的排序感兴趣。
为了说明起见，C（m）可能是“如果m 2 + m + 41是素数则返回true，否则返回false”，但我确实在寻找一种通用方法。
只要C(m)如此神奇，您就不能使用任何更好的技术来直接找到您的解决方案，因此您确实需要以a*b递减的顺序遍历所有内容，这就是我要做的：
用所有对初始化一个max-heap，(a, b)使a = b。这意味着堆包含(0, 0), (1, 1), ... , (1.000.000, 1.000.000)。堆应该基于该a * b值。
现在不断：
(a, b)从堆中获取最大对。(a, b)满意C(a * b)。如果是这样，您就完成了。(a, b-1)到堆中（已提供b > 0，否则什么也不做）。这是一个非常简单的O(n log n)时间和O(n)空间算法，只要您能够快速（几次迭代）找到答案即可。这当然取决于C。
如果遇到空间问题，您当然可以通过将问题分成多个子问题来轻松地降低空间复杂度，例如2：
(500.000, 500.000), (500.001, 500.001), ... , (1.000.000, 1.000.000)到堆中并找到最佳配对(a, b)。(0, 0), (1, 1), ... (499.999, 499.999)。本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句