HUST 1606 Naive

Description

Give you a positive integer x, determine whether it is the sum of three positive cubic numbers.

Input

There’re several test cases. For each case: 
Only one line containing an integer x (  1≤x≤10^6)

Output

For each test case, print “Yes” if it is or “No” if it isn’t. 
(See sample for more details)

Sample Input

1
3
10

Sample Output

No
Yes
Yes
判断一个数能不能是三个立方数的和，先预处理一下两个立方数的和，然后询问的时候找一个立方数就好了
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e6+10;
int x,f[maxn];

int main()
{
	for (int i=1;i*i*i<maxn;i++)
	{
		for (int j=i;j*j*j<maxn;j++)
		{
			if (i*i*i+j*j*j<maxn) f[i*i*i+j*j*j]=1;
		}
	}
	while (~scanf("%d",&x))
	{
		int flag=0;
		for (int i=1;i*i*i<=x;i++)
		{
			if (f[x-i*i*i]) {flag=1; break;}
		}
		printf("%s\n",flag?"Yes":"No");
	}
	return 0;
}