JG-OJ记录106：14:平方和-3

描述

已知一个正整数x，问x能否凑成三个互不相同的正整数的平方和。

输入

一个正整数n，表示测试案例的数量。

每组案例由一个正整数x组成（x不大于1e+8）。

输出

针对每组案例，如果x可以表示成三个互不相同的正整数的平方和，那么输出Yes，否则输出No。

每组案例输出完都要换行。

样例输入 复制样例

2

30

10

样例输出

Yes

No

HINT

30=1*1+2*2+5*5

解：

三次循环会超时（TLE）

分析题目，三个互不相同的正整数的平方和，所以一个数一定小于全部的三分一，由此突破

#include<iostream> #include<cmath> using namespace std; int pd(long long int x) { int sq; for(int i=1;(i*i)<(x/3);i++) { for(int j=i+1;(j*j)<=((x-(i*i))/2);j++) { int q=x-(i*i)-(j*j); sq=sqrt(q); if((sq*sq==q)&&(sq!=i)&&(sq!=j)) { return 1; } } } return 0; } int main() { int n; int m=0; cin>>n; for(int i=1;i<=n;i++) { m=0; long long int a; cin>>a; m=pd(a); if(m) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }