GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A33419. $完全平方数题面描述小杨同学有一个包含n个非负整数的序列A，他想要知道其中有多少对下标组合 <i,j>( 1\leqi , j\leqn , i<j )，使得 Ai + Aj 是完全平方数。如果x是完全平方数，则存在非负整数y使得 y * y = x。$

填空题中等

知识点

完全平方数枚举双重循环

题目描述

完全平方数 题面描述 小杨同学有一个包含n个非负整数的序列A，他想要知道其中有多少对下标组合 <i,j>( 1\leqi , j\leqn , i<j )，使得 A i + A j 是完全平方数。 如果x是完全平方数，则存在非负整数y使得 y * y = x。 输入格式 第一行一个非负整数n，表示非负整数个数。 第二行包含n个非负整数 A 1, A 2 ...... A n ，表示序列A包含的非负整数。 输出格式 输出一个非负整数，表示和是完全平方数的非负整数对数。 输入样例 5 1 4 3 3 5 输出样例 3

参考答案

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main(){
  int n;
  cin >> n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      int m = a[i] + a[j];
      int t = sqrt(m + 1e-7);
      if(t * t == m)
        ans++;
    }
  }
  cout<<ans<<"\n";
}

上一题下一题