Problem


Key Idea

Transpose \(a^3\).
It becomes finding value b which is \(b = \sqrt[3]{x-a^3}\).
And it can be solved with brute force.
Took some time for me to find a way to tell wether b is integer or not.

  • Time: \(O(\sqrt[3]x)\)
  • Space: \(O(1)\)


Implementation

/**
 * author: jooncco
 * written: 2022. 9. 6. Tue. 00:05:14 [UTC+9]
 **/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    private final static FastScanner sc= new FastScanner();
    private static final Long mx= 1000000000000L;
 
    public static void main(String[] args) {
        Set<Long> cubes= new HashSet<>();
        preCalc(cubes);
 
        long t,x; t= sc.nextLong();
        while (t-- > 0) {
            x= sc.nextLong();
            boolean yes= false;
            for (long a= 1; a*a*a <= x; ++a) {
                if (cubes.contains(x - a*a*a)) {
                    yes= true;
                    break;
                }
            }
            System.out.println(yes ? "YES":"NO");
        }
    }
 
    private static void preCalc(Set<Long> cubes) {
        for (long i=1; i*i*i <= mx; ++i) {
            cubes.add(i*i*i);
        }
    }
 
}

class FastScanner {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st=new StringTokenizer("");
    String next() {
        while (!st.hasMoreTokens()) {
            try {
                st=new StringTokenizer(br.readLine());
            } catch (IOException e) {}
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
}

Leave a comment