题目背景
2025 年海淀区中小学生信息学竞赛小学组复赛题目,数据为洛谷自造。
为更好区分不同时间复杂度的做法,本题时间限制下调到 500 毫秒。
题目描述
陶陶是一个计算机爱好者,对二进制数有着特别的喜好,遇到各种各样的数据,他总能找到跟 2 的整数次幂的关系。现在,他获得了一个长度为 n 的数列 a1,a2,…,an,他发现其中有些元素的和恰好是 2 的整数次幂。对于给定的 a1,a2,…,an,你的任务是统计有多少个数对 (i,j) 满足 ai+aj=2x,其中 x∈N∗,i<j,这里 N∗ 表示正整数集合。
输入格式
第一行包含一个整数 n,第二行包含 n 个整数 a1,a2,…,an。
输出格式
仅有一个正整数,表示满足 ai+aj 是 2 的整数次幂的数对 (i,j) 的个数。
提示
- 对于 40% 的数据,1≤n≤103,对于每一个正整数 i,1≤i≤n,都有 1≤ai≤109。
- 对于另外 60% 的数据,1≤n≤105,对于每一个正整数 i,1≤i≤n,都有 1≤ai≤109。