救救Schelski(毒瘤脑洞题&校赛题解)
救救Schelski(毒瘤脑洞题&校赛题解)
这道题是校赛上遇见的,题面极其毒瘤,也不知道谁出的,题目本质靠脑洞,记录一下。
题面
可怜的Schelski为了改变自己是一个菜鸡的事实,终日沉迷"学习"无法自拔,以至于都二十多岁了还是单身。
这一天他终于遇见了一位同样沉迷于学习的小姐姐,为了追求小姐姐,Schelski必须解决小姐姐为他出的难题。
小姐姐对素数情有独钟,她想让Schelski帮忙研究素数与立方数之间的关系,这可难倒了数学水平还停留在小学四年级奥赛程度的Schelski。
你能够帮助Schelski脱单吗? 请你帮助他判断某个素数是否可能由两个数的立方差所得到。
输入
第一行输入一个整数t(1<=t<=100),表示询问次数。
接下来的t行每行有一个素数p(2<=p<=10^12)。
输出
对于每次询问,如果可能则输出“YES”,否则输出“NO”。
样例输入
5
7
13
23
2269
5557
样例输出
YES
NO
NO
YES
NO
话不多说 上代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int main()
{
ll t;
ll p;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&p);
p-=7;
if(p==0)
{
printf("YES\n");
continue;
}
if(p%3!=0)
{
printf("NO\n");
}
else
{
p/=3;
double q=p;
double r=sqrt(9+4*q);
if((int)(r)!=r)
{
printf("NO\n");
continue;
}
double h=(r-3)/2;
if((int)(h)!=h||h<=0)
{
printf("NO\n");
continue;
}
printf("YES\n");
}
}
return 0;
}