3.1 编程题 1
试题名称：平方之和
时间限制： 1.0 s
内存限制： 512.0 MB
3.1.1 题面描述
小杨有 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，他想知道对于所有的 $i (1 \leq i \leq n)$，是否存在两个正整数 $x$ 和 $y$ 满足 $x \times x + y \times y = a_i$。
3.1.2 输入格式
第一行包含一个正整数 $n$，代表正整数数量。
接下来有 $n$ 行，每行包含一个正整数 $a_i$。
3.1.3 输出格式
对于每个正整数 $a_i$，如果存在两个正整数 $x$ 和 $y$ 满足 $x \times x + y \times y = a_i$，输出 "Yes"，否则输出 "No"。
3.1.4 样例 1
输入
2 3 5
输出
Yes
No
3.1.5 样例解释
对于第一个样例，1×1 + 2×2 = 5，因此答案为 Yes。
3.1.6 数据范围
$ 1 \leq n \leq 10 ^ 4, 1 \leq a_i \leq 10 ^ 6 $
3.1.7 参考程序
#include <bits/stdc++.h>
using namespace std;
bool check(int n) {
for (int i = 0; i * i <= n; ++i) {
int j = sqrt(n - i * i);
if (i * i + j * j == n) return true;
}
return false;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (check(n)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
参考程序
#include<iostream>
using namespace std;
int main() {
int count = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int N,is_zhe=0;
cin >> N;
for (int j = 1; j < sqrt(N); j++)
{
count++;
cout << count<<endl;
int temp = N - pow(j, 2);
int emp = sqrt(temp);
if (temp == pow(emp, 2)){
is_zhe=1;
break;
}
//cout <<temp <<" " << pow(emp, 2) << endl;
}
if (is_zhe)
{
cout << "Yes"<<endl;
}else{
cout << "No" << endl;
}
}
return 0;
}
