订单(a,b)由a*b的结果对

Question

我想找到满足某些条件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 ² + m + 41是素数则返回true,否则返回false",但我真的在寻找一种通用方法.

Answer 1

如果这C(m)是如此神奇，以至于您无法使用任何更好的技术来直接找到解决方案，因此您确实需要以a*b降序遍历所有内容，这就是我要做的：

(a, b)使用所有满足以下条件的对初始化最大堆a = b。这意味着堆包含(0, 0), (1, 1), ... , (1.000.000, 1.000.000). 堆应该基于值a * b。

现在连续：

1. (a, b)从堆中获取最大对。
2. 验证是否(a, b)满足C(a * b). 如果是这样，你就完成了。
3. 否则，添加(a, b-1)到堆中（前提是b > 0，否则什么都不做）。

这是一个非常简单的O(n log n)时间和O(n)空间算法，前提是您可以快速找到答案（在几次迭代中）。这当然取决于C。

如果遇到空间问题，您当然可以通过将问题分解为多个子问题（例如 2）来轻松降低空间复杂度：

1. 仅添加(500.000, 500.000), (500.001, 500.001), ... , (1.000.000, 1.000.000)到堆中并找到您最好的一对(a, b)。
2. 对 执行同样的操作(0, 0), (1, 1), ... (499.999, 499.999)。
3. 采取两个解决方案中最好的一个。