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

最近我看到，給出瞭解決數論問題，我需要找到對（X，Y）的量x^k + y^k = n，其中給出k和n。我唯一的解決方案是暴力破解所有可能的x，y對，並檢查它們是否等於n。但是，我需要做的是爲大n和k，1 < = N < = 10^18，1 < = K < = 100。什麼是最有效的方法呢？查找量，其中x-1K-+ Y^K = N

來源

2017-04-07 MRMKR

許多可能的優化，但第一個：不需要強制*對*。對於每個候選'x'，找到'n - x^k'並確定它是否是第k次方。（當然，你需要特殊情況'k = 1'，並且'k = 2'也有數字理論技巧可用。） –

'x'和'y'是* positive *？ –

@DmitryBychenko是的，x和y是自然數 – MRMKR

一種可能的方法是使用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））

來源

2017-04-07 11:09:13 qwertyman

如果n <= 10^18'和'k == 2'然後我們必須計算多達*十億*項... –

謝謝，好點，我編輯了答案。 – qwertyman

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

回答

相關問題