湘潭校赛 Bob's Problem

Bob's Problem
Accepted : 18		Submit : 115
Time Limit : 1000 MS		Memory Limit : 65536 KB

题目描述

Bob今天碰到一个问题，他想知道x³+y³ = c 是否存在正整数解？

输入

第一行是一个整数K(K≤20000)，表示样例的个数。以后每行一个整数c(2≤c≤10⁹)

输出

每行输出一个样例的结果，如果存在，输出“Yes”，否则输出“No”。（引号不用输出）

样例输入

样例输出

Yes

No

哈希

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 using namespace std;

 const int INF =  ;

 int a[];

 struct node

 {

     int num;

     struct node *next;

 };

 struct node f[INF];

 void Insert(int x)

 {

     struct node *p,*q;

     int k;

     k=x%INF;

     p=&f[k];

     while( p!=NULL && p->num!=x)

     {

         p=p->next;

     }

     if( p==NULL )

     {

         q=(struct node*)malloc(sizeof(struct node));

         q->next=f[k].next;

         q->num=x;

         f[k].next=q;

     }

 }

 bool found(int x)

 {

     int k;

     struct node *p;

     k=x%INF;

     p=&f[k];

     while( p!=NULL && p->num!=x)

     {

         p=p->next;

     }

     if( p==NULL)

     return false;

     if( p->num==x)

         return true;

 }

 void prepare()

 {

     int i,j;

     for(i=;i<=;i++)

         a[i]=i*i*i;

     for(i=;i<INF;i++)

     {

         f[i].num=;

         f[i].next=NULL;

     }

     for(i=;i<=;i++)

         for(j=i;j<=;j++)

         {

             Insert(a[i]+a[j]);

         }

 }

 int main()

 {

     int n,i,x;

     prepare();

     while(scanf("%d",&n)>)

     {

         for(i=;i<=n;i++)

         {

             scanf("%d",&x);

             if( found(x)==true )

                 printf("Yes\n");

             else printf("No\n");

         }

     }

     return ;

 }

set

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 #include<set>

 #include<algorithm>

 using namespace std;

 int a[];

 set<int> Q;

 void prepare()

 {

     int i,j;

     for(i=;i<=;i++)

         a[i]=i*i*i;

     Q.clear();

     for(i=;i<=;i++)

         for(j=i;j<=;j++)

             Q.insert(a[i]+a[j]);

 }

 int main()

 {

     int T,n;

     prepare();

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         int flag=Q.count(n);

         if(flag==)printf("No\n");

         else printf("Yes\n");

     }

     return ;

 }

巴特西

湘潭校赛 Bob's Problem

Bob's Problem

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章