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;
}