Codeforces Round 702 (Div. 3) - Sum of Cubes 링크
(2023.08.24 기준 Difficulty *1100)

문제

x가 주어질 때, a³+b³=x를 만족하는 양의 정수 a, b가 있는지 판별

알고리즘

적당한 가지치기를 곁들인 브루트포스

풀이

x는 최대 1e12이다. 그러므로 각 수의 최대는 10,000 미만이다.
그러므로 1~9999 까지의 세제곱을 전부 구해놓자.

변수는 a와 b, 2개이다. 서로 독립적이므로 일단, a는 1~9999까지 하나하나 살펴볼 수 밖에 없다.
a가 정해지면 b³는 x-a³이 되어야 하므로 최대 범위가 정해져 있으며, x가 양수인 삼차함수는 증가 그래프이므로 이분 탐색을 사용할 수 있게 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll cube[10000];

bool solve(){
    ll x; cin >> x;

    // a는 [1, 9999] 전부 검사
    for (ll a = 1; a <= 9999; a++){
        if (cube[a] >= x) return false;

        // b는 [1, 9999] 구간에서 이분 탐색으로 가능한 수 찾기
        int st = 1, en = 9999;
        while (st < en){
            int mid = (st + en) >> 1;
            if (cube[a] + cube[mid] < x) st = mid + 1;
            else en = mid;
        }

        // a^3 + b^3 = x
        if (cube[a] + cube[st] == x) return true;
    }

    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // x는 최대 1e12이므로 각 변수의 최대는 10000 미만
    // 9999까지의 세제곱을 전처리
    for (ll i = 1; i <= 9999; i++) cube[i] = i * i * i;

    int t; cin >> t;
    while (t--) cout << (solve() ? "YES" : "NO") << '\n';
}

• Python

import sys; input = sys.stdin.readline

# x는 최대 1e12이므로 각 변수의 최대는 10000 미만
# 9999까지의 세제곱을 전처리
cube = [0] * 10000
for i in range(1, 10000):
    cube[i] = i ** 3

def solve():
    x = int(input())

    # a는 [1, 9999] 전부 검사
    for a in range(1, 10000):
        if cube[a] >= x:
            return False

        # b는 [1, 9999] 구간에서 이분 탐색으로 가능한 수 찾기
        st = 1; en = 9999
        while st < en:
            mid = (st + en) >> 1
            if cube[a] + cube[mid] < x:
                st = mid + 1
            else:
                en = mid

        # a^3 + b^3 = x
        if cube[a] + cube[st] == x:
            return True

    return False;

for _ in range(int(input())):
    print('YES' if solve() else 'NO')