找出所有四元组[a，b，c，d]，其中当1 <= a，b，c或d <= 10000时a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3 [英] Find all the quadruples [a, b, c, d] where a^3 + b^3 = c^3 + d^3 when 1 &lt;= a, b, c or d &lt;= 10000

问题描述

正在寻找算法或一些编码提示来找到解决方案

Looking for an algorithm or some coding hints to find the solutions for

a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3 ，其中 a，b，c和d 都在 [1 .. 10000]范围内

这是一个面试问题。

我在考虑优先级队列至少要进行迭代 a 和 b 的值。一些提示会很棒，将尝试从那里开始。

I'm thinking priority queues to at least iterate for a and b values. Some hint will be great, will try to work through from there.

推荐答案

使用哈希映射存储（cube，（a，b）），您可以迭代所有可能的整数对，并在发现映射中已经存在所需的多维数据集之和后输出解决方案。

Using a hash map to store the (cube,(a,b)), you can iterate all possible pairs of integers, and output a solution once you have found that the required sum of cubes is already in the 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）空间^（1）和O（n ^ 2 + OUTPUT）时间，其中OUTPUT是输出的大小。

This solution is O(n^2) space⁽¹⁾ and O(n^2 + OUTPUT) time on average, where OUTPUT is the size of the output.

编辑：

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

Required space is actually O(n^2 logn), where n is the range (10^5), because to represent 10^5 integers you need ceil(log_2(10^15)) = 50 bits. So, you actually need something like 500,000,000,000 bits (+ overhead for map and list) which is ~58.2 GB (+ overhead).

因为对于大多数计算机而言，这有点太多-您可能要考虑将数据存储在磁盘上，或者如果您拥有64位计算机-只需存储在内存中，然后让操作系统和虚拟内存系统会尽其所能。

Since for most machines it is a bit too much - you might want to consider storing the data on disk, or if you have 64bits machine - just store in into "memory" and let the OS and virtual memory system do this as best as it can.

（ 1）正如修改所阐明的，它实际上是 O（n ^ 2log（n））空间，但是如果我们将每个整数存储都当作 O（ 1）（通常是这种情况），我们得到 O（n ^ 2）空间。显然，时间复杂度也适用相同的原理。

(1) As the edit clarifies, it is actually O(n^2log(n)) space, however if we take each integer storage as O(1) (which is usually the case) we get O(n^2) space. Same principle will apply for the time complexity, obviously.

这篇关于找出所有四元组[a，b，c，d]，其中当1 <= a，b，c或d <= 10000时a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！