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

Luogu
IDLGB4241
Time500ms
Memory512MB
DifficultyP3
二分2025北京哈希 hashing科创活动小学活动
陶陶是一个计算机爱好者,对二进制数有着特别的喜好,遇到各种各样的数据,他总能找到跟 $2$ 的整数次幂的关系。现在,他获得了一个长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$,他发现其中有些元素的和恰好是 $2$ 的整数次幂。对于给定的 $a_1, a_2, \dots, a_n$,你的任务是统计有多少个数对 $(i, j)$ 满足 $a_i + a_j = 2^x$,其中 $x \in \N^*$,$i < j$,这里 $\N^*$ 表示正整数集合。 ## Input 第一行包含一个整数 $n$,第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。 ## Output 仅有一个正整数,表示满足 $a_i + a_j$ 是 $2$ 的整数次幂的数对 $(i, j)$ 的个数。 [samples] ## Background 2024 年海淀区中小学生信息学竞赛小学组复赛题目,数据为洛谷自造。 为更好区分不同时间复杂度的做法,本题时间限制下调到 500 毫秒。 ## Note - 对于 $40\%$ 的数据,$1 \leq n \leq 10^3$,对于每一个正整数 $i$,$1 \leq i \leq n$,都有 $1 \leq a_i \leq 10^9$。 - 对于另外 $60\%$ 的数据,$1 \leq n \leq 10^5$,对于每一个正整数 $i$,$1 \leq i \leq n$,都有 $1 \leq a_i \leq 10^9$。
Samples
Input #1
4
7 3 2 1
Output #1
2
Input #2
3
1 1 1
Output #2
3
API Response (JSON)
{
  "problem": {
    "name": "[海淀区小学组 2024] 统计数对",
    "description": {
      "content": "陶陶是一个计算机爱好者,对二进制数有着特别的喜好,遇到各种各样的数据,他总能找到跟 $2$ 的整数次幂的关系。现在,他获得了一个长度为 $n$ 的数列 $a_1, a_2, \\dots, a_n$,他发现其中有些元素的和恰好是 $2$ 的整数次幂。对于给定的 $a_1, a_2, \\dots, a_n$,你的任务是统计有多少个数对 $(i, j)$ 满足 $a_i + a_j = 2^x$,其中 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4241"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "陶陶是一个计算机爱好者,对二进制数有着特别的喜好,遇到各种各样的数据,他总能找到跟 $2$ 的整数次幂的关系。现在,他获得了一个长度为 $n$ 的数列 $a_1, a_2, \\dots, a_n$,他发现其中有些元素的和恰好是 $2$ 的整数次幂。对于给定的 $a_1, a_2, \\dots, a_n$,你的任务是统计有多少个数对 $(i, j)$ 满足 $a_i + a_j = 2^x$,其中 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments