C++로 두 세제곱수의 합 쌍 찾기

문제 개요

하나의 자연수 n이 주어졌을 때, 이 수를 두 세제곱수의 합으로 표현하는 서로 다른 두 쌍을 찾아야 합니다. 즉, 다음 조건을 만족하는 네 개의 정수 a, b, c, d를 구하는 것이 목표입니다.

n = a³ + b³ = c³ + d³

예를 들어 유명한 라마누잔 수인 1729는 1729 = 1³ + 12³ = 9³ + 10³처럼 두 가지 방법으로 표현되는 대표적인 예입니다.

접근 방법

핵심 아이디어는 매우 단순합니다. a, b, c, d는 모두 n의 세제곱근(n^1/3)보다 작거나 같은 수여야 한다는 점에 착안합니다.

n^1/3 이하의 수들로 만들 수 있는 모든 서로 다른 쌍 (x, y)에 대해 x³ + y³를 계산하고, 그 값이 주어진 수 n과 일치하는 경우만 골라냅니다. 이때 해시 맵(맵 자료구조)을 활용해 이미 발견된 쌍을 저장해 둡니다. 동일한 합이 또 등장하면, 맵에 저장된 첫 번째 쌍과 현재 쌍을 함께 출력하면 됩니다.

알고리즘

getPairs(n):
begin
    cube_root := n의 세제곱근
    키는 int, 값은 pair인 map 선언
    for i in range 1 to cube_root, do
       for j in range i + 1 to cube_root, do
          sum = i³ + j³
          if sum != n 이면 continue로 건너뜀
          if sum이 map에 존재하면 기존 쌍과 (i, j)를 출력
          else (i, j)를 sum과 함께 map에 삽입
       done
    done
end

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

실행 결과

(2, 24) and (18, 20)

실제로 확인해 보면 2³ + 24³ = 8 + 13824 = 13832이고, 18³ + 20³ = 5832 + 8000 = 13832로 두 쌍 모두 동일한 값이 됩니다.

시간 복잡도