C++에서 큐브 쌍 찾기 - (A n^(2/3) 솔루션)

번호가 부여됩니다. 숫자를 두 큐브의 합으로 나타낼 수 있는 두 쌍을 찾아야 합니다. 따라서 주어진 숫자 n이 n =a ³ 으로 표현될 수 있도록 두 쌍 (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)