顺序（A，B）对由A * B的结果 [英] Order (a,b) pairs by result of a*b

问题描述

我想找到的最高值M = A * B满足一些条件C（M），其中

I would like to find the highest value m = a*b that satisfies some condition C(m), where

1 <= a <= b <= 1,000,000.

为了做到这一点，我想遍历所有对A，B从大到小依次为A * B。

In order to do that, I'd like to iterate all pairs of a,b in decreasing order of a*b.

例如，对于值高达5，顺序将是：

For example, for values up to 5, the order would be:

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般的树搜索，在这里我产生候选人目前的访问设置，并选择价值最高的候选人，但它是一个一团糟，我不知道是否正确。我不知道是否有绝招某种我失踪。

So far I've come up with a BFS-like tree search, where I generate candidates from the current "visited" set and pick the highest value candidate, but it's a tangled mess, and I'm not sure about correctness. I wonder if there's some sort of trick I'm missing.

我也通过任何单调函数f（A，B），如果这样的事情存在

I'm also interested in the more general case of ordering by any monotonic function f(a,b), if such a thing exists.

有关说明，C（M）可能是返回true，如果m ² + M + 41为质数，否则返回false，但我真的找一个通用的方法。

For illustration, C(m) could be "return true if m²+m+41 is prime, otherwise return false", but I'm really looking for a general approach.

推荐答案

但 C（M）就是这么神奇，你不能使用任何更好的方法来找到你的解决方案直接，因此，你真的需要遍历所有 A * B 按递减顺序，这是我会做什么：

Provided that C(m) is so magical that you cannot use any better technique to find your solution directly and thus you really need to traverse all a*b in decreasing order, this is what I would do:

初​​始化一个最大堆与所有对（A，B），使得 A = B 。这意味着，堆包含（0,0），（1,1），...，（1000000，1000000）。堆应根据 A * B 值。

Initialize a max-heap with all pairs (a, b) such that a = b. This means that the heap contains (0, 0), (1, 1), ... , (1.000.000, 1.000.000). The heap should be based on the a * b value.

现在不断：

1. 获取最大对（A，B）从堆中。
2. 验证是否（A，B）满足 C（A * B）。如果是这样，你做。
3. 否则，添加（A，B-1）堆（提供 B＆GT; 0 ，否则什么都不做）。

1. Get the max pair (a, b) from the heap.
2. Verify if (a, b) satisfies C(a * b). If so, you are done.
3. Otherwise, add (a, b-1) to the heap (provided b > 0, otherwise do nothing).

这是一个非常简单的为O（n log n）的时间和 O（N）空间算法，提供你找到答案很快（在几个迭代）。当然，这取决于 C 。

This is a very simple O(n log n) time and O(n) space algorithm, provided that you find the answer quickly (in a few iterations). This of course depends on C.

如果您遇到空间问题，你当然可以很容易地通过降低在多个子问题分手了问题的空间复杂度，比如2：

If you run into space problems you can of course easily decrease the space complexity by splitting up the problem in a number of subproblems, for instance 2:

1. 添加仅（500.000，500.000）（500.001，500.001），...，（1000000，1000000）堆，找到你的最好的对（A，B）。
2. 执行相同的（0,0），（1,1），...（499.999，499.999）。
3. 以最好的两种解决方案。

1. Add only (500.000, 500.000), (500.001, 500.001), ... , (1.000.000, 1.000.000) to the heap and find your best pair (a, b).
2. Do the same for (0, 0), (1, 1), ... (499.999, 499.999).
3. Take the best of the two solutions.

这篇关于顺序（A，B）对由A * B的结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！