如何找到所有小于N的出租车号码？ [英] How to find all taxicab numbers less than N?

问题描述

出租车的编号是一个整数，可以用两种不同的方式表示为两个整数立方体的总和： a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3 。设计一种算法来查找a，b，c和d小于N的所有出租车编号。

A taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: a^3+b^3 = c^3+d^3. Design an algorithm to find all taxicab numbers with a, b, c, and d less than N.

请同时给出以N为单位的时空复杂度b $ b我可以在 o（N ^ 2.logN）的时间内完成 O（N ^ 2）空间。

Please give both the space and time complexity in terms of N. I could do it in o(N^2.logN) time with O(N^2) space.

到目前为止我发现的最佳算法：

Best algorithm I've found so far:

形成所有对： N ^ 2

对总和进行排序： N ^ 2 logN

查找小于N的重复项

Form all pairs: N^2
Sort the sum: N^2 logN
Find duplicates less than N

但这需要 N ^ 2 空间。我们可以做得更好吗？

But this takes N^2 space. Can we do better?

推荐答案

算法的时间复杂度不能小于 O（N ² ），因为您最多可以打印 O（N ² ）个出租车编号。

The time complexity of the algorithm can't be less than O(N²) in any case, since you might print up to O(N²) taxicab numbers.

从理论上讲，为减少空间使用，您可以使用此处提到的建议：小链接。基本上，这个想法是，首先尝试所有可能的对 a，b 并找到解决方案：

To reduce space usage you could, in theory, use the suggestion mentioned here: little link. Basically, the idea is that first you try all possible pairs a, b and find the solution to this:

a = 1 −（p − 3 * q）（p ² + 3 * q ² ）

a = 1 − (p − 3 * q)(p² + 3 * q²)

b = −1 +（p + 3 * q）（p ² + 3q ² ）

b = −1 + (p + 3 * q)(p² + 3q²)

然后您可以使用以下方法找到合适的 c，d 对：

Then you can find the appropriate c, d pair using:

c =（ p + 3 * q）-（p ² + 3 * q ² ）

c = (p + 3 * q) - (p² + 3 * q²)

d =-（p -3 * q）+（p ² + 3 * q ² ）

d = -(p - 3 * q) + (p² + 3 * q²)

并检查它们是否都小于N。这里的问题是，求解方程组可能会有些混乱（有点我的意思是非常乏味）。

and check whether they are both less than N. The issue here is that solving that system of equations might get a bit messy (by 'a bit' I mean very tedious).

O（N ² ）空间解决方案要简单得多，并且由于任何二次时间，它可能都足够高效可以在合理的时间限制内运行的复杂性可能会很好二次空间使用。

The O(N²) space solution is much simpler, and it'd probably be efficient enough since anything of quadratic time complexity that can run in reasonable time limits will probably be fine with quadratic space usage.

我希望能有所帮助！

这篇关于如何找到所有小于N的出租车号码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！