luogu#B4241. [海淀区小学组 2025] 统计数对
[海淀区小学组 2025] 统计数对
题目背景
2025 年海淀区中小学生信息学竞赛小学组复赛题目,数据为洛谷自造。
为更好区分不同时间复杂度的做法,本题时间限制下调到 500 毫秒。
题目描述
陶陶是一个计算机爱好者,对二进制数有着特别的喜好,遇到各种各样的数据,他总能找到跟 的整数次幂的关系。现在,他获得了一个长度为 的数列 ,他发现其中有些元素的和恰好是 的整数次幂。对于给定的 ,你的任务是统计有多少个数对 满足 ,其中 ,,这里 表示正整数集合。
输入格式
第一行包含一个整数 ,第二行包含 个整数 。
输出格式
仅有一个正整数,表示满足 是 的整数次幂的数对 的个数。
4
7 3 2 1
2
3
1 1 1
3
提示
- 对于 的数据,,对于每一个正整数 ,,都有 。
- 对于另外 的数据,,对于每一个正整数 ,,都有 。