[Codeforces] 1490C. Sum of Cubes explained
![title image](/public/images/codeforces-teaser.png)
Problem
Approach
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.
Code
/**
* 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());
}
}
Complexity
- Time: \(O(\sqrt[3]x)\)
- Space: \(O(1)\)
Leave a comment