牛客——黑魔法师

链接：https://www.nowcoder.com/acm/contest/215/A 来源：牛客网  

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld

题目描述

“White shores, and beyond. A far green country under a swift sunrise.”--灰魔法师 给出长度为n的序列a, 求有多少对数对 (i, j) (1 <= i < j <= n) 满足 ai + aj 为完全平方数。

输入描述:

第一行一个整数 n (1 <= n <= 105) 第二行 n 个整数 ai (1 <= ai <= 105)

输出描述:

输出一个整数，表示满足上述条件的数对个数。

示例1

输入

复制

3 1 3 6

输出

复制

2

说明

满足条件的有 (1, 2), (2, 3) 两对。

 这个是牛客上的一个小比赛的签到题，是最简单的一道，而且过得人也比较多，当时我感觉我也能坐，最后我发现我想多了，写了半年也没有写出来，其实写是非常好写的，但是就是容易超时，所以必须优化，最后还是看了别人的代码才把这道题给敲了出来，唉，归根究底还是自己太菜了吧，以后继续好好的刷题吧，没有什么是·一蹴而就的，下面给出AC代码。

#include<stdio.h> #include<string.h> using namespace std; #define ll long long ll a[5000] ; ll b[100007]; int main() { memset(b,0,sizeof(b)); ll n,cnt,m; cnt=1; for(ll i=1;i*i<=200000;i++) a[cnt++]=i*i; //打表，先把平方的值给打印下来； scanf("%lld",&n); for(ll i=1;i<=n;i++) { scanf("%lld",&m); b[m]++; } //因为是100000个数，而且每个 //数的值都小于100000，所以我们可以判断出里面会有很多的重复的数字，把那些重复的数字统计起来，减小运行的时间； ll ans1=0,ans2=0; for(ll i=1;i<cnt;i++) { for(ll j=1;j<=100000;j++) { if(b[j]==0)continue; ll tmp=a[i]-j; if(tmp>100000) continue; if(tmp<=0) break; if(b[tmp]) { if(tmp==j) ans1+=(b[j]*(b[j]-1))/2; else ans2+=b[j]*b[tmp]; } } } ans1=ans1+ans2/2; printf("%lld",ans1); return 0; }