C. Sum of Cubes
一、题目
You are given a positive integer x. Check whether the number x is representable as the sum of the cubes of two positive integers.
Formally, you need to check if there are two integers a and b (1≤a,b) such that a^3 b^3=x.
For example, if x=35, then the numbers a=2 and b=3 are suitable (2^3 3^3=8 27=35). If x=4, then no pair of numbers a and b is suitable.
两个数能否表示为立方和？
二、输入
The first line contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow.
Each test case contains one integer x (1≤x≤1e12).
Please note, that the input for some test cases won’t fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language.
第一行测试样例数t
每个样例一个数x
三、输出
YES/NO
四、样例
input:
7124343516703657519796output:
NOYESNONOYESYESYESNote
The number 1 is not representable as the sum of two cubes.
The number 2 is represented as 1^3 1^3.
The number 4 is not representable as the sum of two cubes.
The number 34 is not representable as the sum of two cubes.
The number 35 is represented as 2^3 3^3.
The number 16 is represented as 2^3 2^3.
The number 703657519796 is represented as 5^7793 7^9933.
五、思路 代码
打表然后二分查找
不打表直接暴力，或者打表不用二分都会超时，不要问我是怎么知道的…
数据很大要用long long，打表只需打到1e4，打表时遍历用的i要用long long，这种低级错误恐怕只有我会犯了
代码如下：
#include<iostream>#include<cmath>#include<algorithm>using namespace std;typedef long long ll;ll g[10004], x;int main() {int t;cin >> t;for(ll i = 1; i <= 10000; i ) g[i] = i * i * i;while (t--) {cin >> x;int f = 0;for(int i = 1; g[i] < x / 2 1; i ) {ll tmp = x - g[i];int l = 1, r = 10000;while (l < r) {int mid = (l r) >> 1;if (g[mid] < tmp) {l = mid 1;}else {r = mid;}}if (g[l] == tmp) {f = 1;break;}}if (f) cout << "YES" << endl;else cout << "NO" << endl;}return 0;}