题目
C. Sum of Cubes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
您将获得一个正整数x.检查号码是否x可表示为两个正整数的立方体之和。
正式地说，您需要检查是否有两个整数a和b (1≤a，b1≤a，b） 使得一个a3+b3=x.
例如，如果x=35，则数字a=2和b=3是合适的（2^3+3^3=8+27=35）。如果x=4，则没有一对数字 a和b是合适的。
Input
第一行包含一个整数t (1≤t≤100） ― 测试用例的数量。然后tt测试用例如下。
每个测试用例包含一个整数x (1≤x≤10^12).
请注意，某些测试用例的输入不适合32-位整数类型，因此应至少使用64编程语言中的 -位整数类型。
Output
对于每个测试用例，在单独的行上输出：
- "YES"如果x可表示为两个正整数的立方体之和。
- "NO" otherwise.
您可以在任何情况下输出“是”和“否”（例如，字符串 yEs, yes, Yes 和YES将被识别为正）。
Example
input
Copy
7 1 2 4 34 35 16 703657519796
output
Copy
NO YES NO NO YES YES YES
Note
号码1不能表示为两个多维数据集的总和。
号码2表示为1^3+1^3.
号码4不能表示为两个多维数据集的总和。
号码34不能表示为两个多维数据集的总和。
号码35表示为2^3+3^3.
号码16表示为2^3+2^3.
号码703657519796表示为5779^3+7993^3.
代码
/*二分法*/
#include <iostream>
#include <math.h>
using namespace std;int main()
{long long t,x,mid,left,right;//left为查找时的左端点，right为右，mid为中点cin >>t;while(t--){cin >> x;long long i,c=0,a;right=pow(x,1.0/3)+10;/*因为pow的返回值为浮点型，而right为长整型，所以加上一个略大的数消去误差，确保所求点在右端点左侧*/for(i=1;i<right;i++){if(i*i*i>=x)//如果i^3大，则后面全大，无需再找break;a=x-i*i*i;//减法可防超限，求另一个加数left=1;while(left<right)//当left>=right时结束{mid=left+((right-left)>>1);//(right-left)>>1相当于(right-left)/2取整//left+((right-left)>>1)不写成(right+left)/2为防止超限if(mid*mid*mid>=a)/*此时说明中点右侧大于所要数，则右侧可全舍去，让中点成为新的右端点，再次重复前一步操作寻找所求数*/right=mid;else//mid*mid*mid<a时，left=mid算式也不成立，所以直接加一；left=mid+1;}if(left*left*left==a){c=1;break;}}if(c==1)cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}