查找量，其中x-1K-+ Y^K = N

Question

最近我看到，给出了解决数论问题，我需要找到对（X，Y）的量x^k + y^k = n，其中给出k和n。我唯一的解决方案是暴力破解所有可能的x，y对，并检查它们是否等于n。但是，我需要做的是为大n和k，1 < = N < = 10^18，1 < = K < = 100。 什么是最有效的方法呢？

Answer 1

一种可能的方法是使用a hash table。

首先，计算所有的值x ^ķ，为此，结果低于ñ。将每个这样的值添加到散列表中，映射到x（其他方式，而不是其他方式）。

之后，迭代通过键X ^ķ从散列集，并检查是否补体，即 N - X ^ķ也是在哈希集合的密钥。

如果n - X ^ķ也是一个键，则该哈希表将其映射到值y，使得n - X ^ķ = Y ^ķ，我们确定了有效的（X， y）对。

否则，如果n - x ^k不是散列表的关键，那么没有解决方案，其中x是一个元素。

---

对上述基本思想进行了改进。例如，如果找到一个好的对（x，y），那么这意味着（y，x）也是一对好的对。使用这种方法，无法测试n/2以上的x值，因为这会导致已经列举的配对。

---

编辑

正如梅德Bychenko在评论部分指出，存在该方法使用大量内存的情况下，使其不太可行。

此问题是最明显的，其中k = 2，因为随着k增加，有显著更少x值对于其中x ^ķ <ñ。

对于k = 2，可以在不使用哈希表的情况下处理该问题，而是直接检查n-x是否是完美正方形。要检查一个数是否是一个完美的正方形，可以应用sqrt函数并检查结果是否为整数值。

---

的另一种方法，用O（1）空间复杂度对任意k，是使用二进制搜索，用于检查是否N - X ^ķ为整数的第k功率。这在类O中具有时间复杂度（n ^1/k * log（n））