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