Tìm các cặp khối lập phương - (A n ^ (2/3) Lời giải) trong C ++

Một con số được đưa ra. Chúng ta phải tìm hai cặp, có thể biểu diễn số dưới dạng tổng của hai khối. Vì vậy, chúng ta phải tìm hai cặp (a, b) và (c, d) sao cho số n đã cho có thể được biểu diễn thành n =a ³ + b ³ =c ³ + d ³

Ý tưởng là đơn giản. Ở đây mọi số a, b, c và d đều nhỏ hơn n ^1/3 . Đối với mọi cặp riêng biệt (x, y) được tạo thành bởi số nhỏ hơn n ^1/3 , nếu tổng của chúng (x ³ + y ³ ) bằng số đã cho, chúng tôi lưu trữ chúng vào bảng băm với giá trị tổng là khóa, sau đó nếu tổng lại xuất hiện, chúng chỉ cần in từng cặp

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

(2, 24) and (18, 20)