最近、私はx^yの解を与える対の量（x、y） k + y^k = nであり、kとnは与えられる。私が来た唯一の解決策は、x、yの可能なすべてのペアをブルートフォースし、それらがnに等しいかどうかをチェックすることです。しかし、大きなnとkのためにそれをする必要があります。1 < = n < = 10^18,1 1 < = k < = 100です。 これを行う最も効率的な方法は何ですか？x^k + y^k = nの対の量を求めよ。
可能なアプローチの1つは、a hash tableです。
まず、結果がn未満のすべての値x kを計算します。そのような各値をハッシュテーブルに追加して、x k - > xをマッピングします（逆の方法ではありません。
その後、キーXハッシュセットからKを反復し、即ち N 、補体かどうかをチェック - X Kもハッシュセット内のキーです。
N場合 - X Kは、またキーである、ハッシュ・テーブルは、値yにそれをマップする、ようにN - X K = Y K、我々は、有効な（Xを同定し、 y）対を生成する。
n - x kがハッシュテーブルのキーでない場合、xが1つの要素である解はありません。
上記の基本的な考え方に改善があります。例えば、良いペア（x、y）が見つかった場合、この（y、x）の意味も良いペアです。これを使用すると、n/2より上のx値をテストすることはできません。これは、すでにペアが列挙されているためです。
EDIT
ドミトリーBychenkoは、コメント欄で述べたように、このアプローチは、それが少ない可能作り、大量のメモリを使用する状況があります。
この問題は、kが増加すると、x k < nのx値が大幅に少なくなるため、k = 2の場合に最も顕著になります。
k = 2の場合、ハッシュテーブルを使用せずに、n - x が完全な正方形かどうかを直接チェックすることで問題に近づくことができます。数値が完全な正方形かどうかを調べるには、sqrt関数を適用して結果が整数値かどうかを調べることができます。 X K整数のk番目のパワーである -
別のアプローチは、任意のkに対するO（1）空間の複雑で、nは、かどうかをチェックするためのバイナリ検索を使用することです。これは、クラスO（n 1/k * log（n））の時間の複雑さを持っています
'n <= 10^18'と' k == 2とすると、我々は数十億円のアイテムを計算しなければならない... –
ありがとう、良い点、私は答えを編集した。 – qwertyman
多くの可能な最適化が、最初のものです。*対*を強要する必要はありません。各候補xについて、n-x^kを見つけて、それがk番目の力であるかどうかを調べる。（もちろん、特別な場合は 'k = 1 'にする必要があり、' k = 2'でも利用可能な数値論的なテクニックがあります） –
'x'と' y'は*正*にしますか？ –
@DmitryBychenkoはい、xとyは自然数です。 – MRMKR