題干：

給出長度為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

說明

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

解題報(bào)告：

? ? 這題不算難，但是我想知道為啥帶個(gè)log就wa？

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 3e5 + 5; int box[MAX]; int main() {int n;scanf("%d",&n);ll ans=0;for(int i=1; i<=n; i++) {int t;scanf("%d",&t);for(int j=2; j<=500; j++) {if(j*j>t) ans+=box[j*j-t];}box[t]++;}printf("%lld",ans);return 0; }

WA代碼：（還是說這種做法就不對(duì)？）

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; int n,tot; ll biao[505000]; ll a[100005]; int main() {cin>>n;for(ll i = 1; i*i<=(ll)7e5; i++) {biao[++tot] = i*i; // printf("%d\n",biao[i]);}for(int i = 1; i<=n; i++) {scanf("%lld",a+i);}sort(a+1,a+n+1);ll ans = 0;for(int i = 1; i<=n; i++) {for(int j = 1; j<=tot; j++) {if(biao[j]-a[i] < a[1] || biao[j]-a[i] > a[n]) continue;if(binary_search(a+1,a+n+1,biao[j]-a[i])) {ans += upper_bound(a+1,a+n+1,biao[j]-a[i]) - lower_bound(a+1,a+n+1,biao[j]-a[i]);}}}printf("%lld\n",ans/2);return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 125A】灰魔法师（打表，暴力）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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