【牛客 - 125A】灰魔法师（打表，暴力）

网友投稿 611 2022-11-26 09:45:31

【牛客 - 125A】灰魔法师（打表，暴力）

题干：

给出长度为n的序列a, 求有多少对数对 (i, j) (1 <= i < j <= n) 满足 ai + aj 为完全平方数。

输入描述:

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

输出描述:

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

示例1

输入

复制

31 3 6

输出

复制

2

说明

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

解题报告：

这题不算难，但是我想知道为啥带个log就wa？

AC代码：

#include#include#include#include#include#include#include#include#include#include#define ll long long#define pb push_back#define pm make_pair#define fi first#define se secondusing 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代码：（还是说这种做法就不对？）

#include#include#include#include#include#include#include#include#include#include#define ll long long#define pb push_back#define pm make_pair#define fi first#define se secondusing 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 ;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：输入 代码 序列 输出 示例
上一篇:*【CodeForces - 1150D】Three Religions（dp，预处理，思维）
下一篇:Oracle两个比较常用把查询结果作为一张表查询的sql语句
相关文章