鏈接：https://www.nowcoder.com/acm/contest/215/A
來(lái)源：牛客網(wǎng)
?

時(shí)間限制：C/C++ 1秒，其他語(yǔ)言2秒
空間限制：C/C++ 262144K，其他語(yǔ)言524288K
64bit IO Format: %lld

題目描述

“White shores, and beyond. A far green country under a swift sunrise.”--灰魔法師

給出長(zhǎng)度為n的序列a, 求有多少對(duì)數(shù)對(duì) (i, j) (1 <= i < j <= n) 滿足 ai + aj 為完全平方數(shù)。

輸入描述:

第一行一個(gè)整數(shù) n (1 <= n <= 105) 第二行 n 個(gè)整數(shù) ai (1 <= ai <= 105)

輸出描述:

輸出一個(gè)整數(shù)，表示滿足上述條件的數(shù)對(duì)個(gè)數(shù)。

示例1

輸入

復(fù)制

3 1 3 6

輸出

復(fù)制

2

說(shuō)明

滿足條件的有 (1, 2), (2, 3) 兩對(duì)。

?這個(gè)是牛客上的一個(gè)小比賽的簽到題，是最簡(jiǎn)單的一道，而且過(guò)得人也比較多，當(dāng)時(shí)我感覺(jué)我也能坐，最后我發(fā)現(xiàn)我想多了，寫了半年也沒(méi)有寫出來(lái)，其實(shí)寫是非常好寫的，但是就是容易超時(shí)，所以必須優(yōu)化，最后還是看了別人的代碼才把這道題給敲了出來(lái)，唉，歸根究底還是自己太菜了吧，以后繼續(xù)好好的刷題吧，沒(méi)有什么是·一蹴而就的，下面給出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; //打表，先把平方的值給打印下來(lái)；scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld",&m);b[m]++;} //因?yàn)槭?00000個(gè)數(shù)，而且每個(gè)//數(shù)的值都小于100000，所以我們可以判斷出里面會(huì)有很多的重復(fù)的數(shù)字，把那些重復(fù)的數(shù)字統(tǒng)計(jì)起來(lái)，減小運(yùn)行的時(shí)間；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; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客——黑魔法师的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。