gesp(三级)（10）洛谷：B3957：[GESP202403 三级] 完全平方数

gesp(三级)（10）洛谷：B3957：[GESP202403 三级] 完全平方数

题目描述

小杨同学有一个包含 n n n 个非负整数的序列 A A A，他想要知道其中有多少对下标组合 < i , j > <i,j> <i,j>（ 1 ≤ i < j ≤ n 1 \leq i < j \leq n 1≤i<j≤n），使得 A i + A j A_i + A_j Ai​+Aj​ 是完全平方数。

如果 x x x 是完全平方数，则存在非负整数 y y y 使得 y × y = x y \times y = x y×y=x。

输入格式

第一行一个非负整数 n n n，表示非负整数个数。
第二入行包含 n n n 个非负整数 A 1 , A 2 , … A n A_1, A_2, \dots A_n A1​,A2​,…An​，表示序列 A A A 包含的非负整数。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

5
1 4 3 3 5

样例输出 #1

3

提示

对全部的测试数据，保证 1 ≤ n ≤ 1000 1 \leq n \leq 1000 1≤n≤1000， 0 ≤ A i ≤ 1 0 5 0 \leq A_i \leq 10^5 0≤Ai​≤105。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
int n,a[1010],cnt=0;
//判断一个非负整数是否是完全平方数 
bool check(int x){
	int m=sqrt(x);
	if(m*m==x) return true;
	else return false;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(check(a[i]+a[j])) cnt++; 
		}
	}
	cout<<cnt;
	return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容