algorithm - 找到所有四元组 [a, b, c, d] 其中 a^3 + b^3 = c^3 + d^3 when 1 <= a, b, c or d <= 10000

Question

<分区>

Answer 1

使用 HashMap 存储(cube,(a,b))，可以迭代所有可能的整数对，并在找到所需的立方和后输出解决方案已经在 map 上了。

伪代码:

map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
  for each b in range(a,10^5): //making sure each pair repeats only once
     cube <- a^3 + b^3
     if map.containsKey(cube):
         for each element e in map.get(cube):
            output e.first(), e.last(), a, b //one solution            
     else:
         map.put(cube,new list<pair<int,int>>)
     //for both cases, add the just found pair to the relevant list
     map.get(cube).add(cube,new pair(a,b))  

这个解决方案平均是 O(n^2) 空间⁽¹⁾ 和 O(n^2 + OUTPUT) 时间，其中 OUTPUT 是输出的大小。

编辑:

所需空间实际上是O(n^2 logn)，其中n是范围(10^5)，因为要表示10^5 整数你需要 ceil(log_2(10^15)) = 50 位。因此，您实际上需要大约 500,000,000,000 位(+ map 和列表的开销)，即 ~58.2 GB(+ 开销)。

因为对于大多数机器来说，它有点太多了 - 你可能想考虑将数据存储在磁盘上，或者如果你有 64 位机器 - 只需存储到“内存”中并让操作系统和 virtual memory系统会尽可能地做到这一点。

---

(1) 正如编辑所阐明的那样，它实际上是 O(n^2log(n)) 空间，但是如果我们将每个整数存储作为 O(1)(通常是这种情况)我们得到 O(n^2) 空间。显然，同样的原则也适用于时间复杂度。