#B4241. [海淀区小学组 2025] 统计数对

    ID: 13240 远端评测题 500ms 512MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>二分2025北京哈希 hashing小学科创活动

[海淀区小学组 2025] 统计数对

题目背景

2025 年海淀区中小学生信息学竞赛小学组复赛题目,数据为洛谷自造。

为更好区分不同时间复杂度的做法,本题时间限制下调到 500 毫秒。

题目描述

陶陶是一个计算机爱好者,对二进制数有着特别的喜好,遇到各种各样的数据,他总能找到跟 22 的整数次幂的关系。现在,他获得了一个长度为 nn 的数列 a1,a2,,ana_1, a_2, \dots, a_n,他发现其中有些元素的和恰好是 22 的整数次幂。对于给定的 a1,a2,,ana_1, a_2, \dots, a_n,你的任务是统计有多少个数对 (i,j)(i, j) 满足 ai+aj=2xa_i + a_j = 2^x,其中 xNx \in \N^*i<ji < j,这里 N\N^* 表示正整数集合。

输入格式

第一行包含一个整数 nn,第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n

输出格式

仅有一个正整数,表示满足 ai+aja_i + a_j22 的整数次幂的数对 (i,j)(i, j) 的个数。

输入数据 1

4
7 3 2 1

输出数据 1

2

输入数据 2

3
1 1 1

输出数据 2

3

提示

  • 对于 40%40\% 的数据,1n1031 \leq n \leq 10^3,对于每一个正整数 ii1in1 \leq i \leq n,都有 1ai1091 \leq a_i \leq 10^9
  • 对于另外 60%60\% 的数据,1n1051 \leq n \leq 10^5,对于每一个正整数 ii1in1 \leq i \leq n,都有 1ai1091 \leq a_i \leq 10^9