最近我看到数论问题，其中我需要找到给出 x^k + y^k = n 的解的对 (x,y) 的数量，其中给出了 k 和 n。我提出的唯一解决方案是暴力破解所有可能的 x,y 对并检查它们是否等于 n。但是我需要为大 n 和 k 做这件事，1 <= n <= 10^18, 1<=k<=100。 最有效的方法是什么？
最佳答案
一种可能的方法是使用 a hash table .
首先，计算所有值 xk，其结果低于 n。将每个这样的值添加到哈希表中，映射 xk -> x(而不是相反，稍后就会清楚为什么)。
然后，遍历哈希集中的键 xk，并检查补码 i.e. n - xk 是否也是哈希集中的一个键。
如果 n - xk 也是一个键，那么哈希表会将它映射到值 y，这样 n - xk = y k，我们确定了一个有效的 (x, y) 对。
否则，如果 n - xk 不是哈希表的键，则无解 x 是一个元素。
上面的基本想法有改进。例如，如果找到一对好 (x, y)，则这意味着 (y, x) 也是一对好。使用此方法，无法测试高于 n/2 的 x 值，因为这会导致已枚举成对。
编辑
正如 Dmitry Bychenko 在评论部分指出的那样，在某些情况下，此方法会使用大量内存，从而降低其可行性。
这个问题在 k = 2 时最为明显，因为随着 k 的增加，xk < n 的 x 值会明显减少。
对于 k = 2，这个问题可以不使用哈希表来解决，而是直接检查 n - x2 是否是一个完美的正方形。要检查一个数是否为完全平方数，可以应用 sqrt 函数并检查结果是否为整数值。
另一种方法，对于任何 k 具有 O(1) 空间复杂度，是使用二进制搜索来检查 n - xk 是否是整数的 k 次方。这在 O(n1/k * log(n))
类中具有时间复杂度关于algorithm - 查找 (x,y) 对的数量，其中 x^k + y^k = n，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43275710/