キューブペアの検索-（A n ^（2/3）ソリューション）C ++

番号が付けられています。 2つの立方体の合計として数を表すことができる2つのペアを見つける必要があります。したがって、与えられた数nがn =a ³ として表現できるように、2つのペア（a、b）と（c、d）を見つける必要があります。 + b ³ =c ³ + d ³

アイデアは単純です。ここで、すべての数a、b、c、およびdはすべてn ^1/3 未満です。 。 n ^1/3 未満の数で形成されるすべての個別のペア（x​​、y）について 、それらの合計（x ³ + y ³ ）が指定された数に等しい場合、合計値をキーとしてハッシュテーブルに格納し、同じ合計が再び発生した場合は、各ペアを出力するだけです

アルゴリズム

getPairs(n):
begin
   cube_root := cube root of n
   map as int type key and pair type value
   for i in range 1 to cube_root, do
      for j in range i + 1 to cube_root, do
         sum = i3 + j3
         if sum is not same as n, then skip next part, go to second iteration
         if sum is present into map, then print pair, and (i, j),
         else insert (i,j) with corresponding sum into the map
      done
   done
end

例

#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int getPairs(int n){
   int cube_root = pow(n, 1.0/3.0);
   map<int, pair<int, int> > my_map;
   for(int i = 1; i<cube_root; i++){
      for(int j = i + 1; j<= cube_root; j++){
         int sum = i*i*i + j*j*j;
         if(sum != n)
         continue;
         if(my_map.find(sum) != my_map.end()){
            cout << "(" << my_map[sum].first << ", " << my_map[sum].second << ") and (" << i << ", " << j << ")" << endl;
         }else{
            my_map[sum] = make_pair(i, j);
         }
      }
   }
}
int main() {
   int n = 13832;
   getPairs(n);
}

出力

(2, 24) and (18, 20)