Tìm cặp lập phương - Giải pháp O(n^(2/3)) trong C++

Cho một số n. Cần tìm hai cặp (a, b) và (c, d) sao cho n = a³ + b³ = c³ + d³.

Ý tưởng: mọi số a, b, c, d đều nhỏ hơn n^(1/3). Với mỗi cặp riêng biệt (x, y) hình thành từ các số nhỏ hơn n^(1/3), nếu tổng lập phương (x³ + y³) bằng n, lưu vào bảng băm với khóa là tổng. Nếu tổng đó xuất hiện lại, in ra cả hai cặp.

Thuật toán

getPairs(n):
    cube_root := căn bậc 3 của n
    map với khóa int và giá trị pair
    cho i từ 1 đến cube_root, làm
        cho j từ i + 1 đến cube_root, làm
            sum = i³ + j³
            nếu sum khác n, bỏ qua, tiếp tục vòng lặp j
            nếu sum đã có trong map, thì in cặp đã lưu và (i, j)
            ngược lại chèn (i,j) với sum tương ứng vào map
        kết thúc
    kết thúc
kết thúc

Ví dụ mã C++

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

Kết quả đầu ra

(2, 24) and (18, 20)