{"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$，其中 $x \\in \\N^*$，$i < j$，这里 $\\N^*$ 表示正整数集合。\n\n## Input\n\n第一行包含一个整数 $n$，第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$。\n\n## Output\n\n仅有一个正整数，表示满足 $a_i + a_j$ 是 $2$ 的整数次幂的数对 $(i, j)$ 的个数。\n\n[samples]\n\n## Background\n\n2024 年海淀区中小学生信息学竞赛小学组复赛题目，数据为洛谷自造。\n\n为更好区分不同时间复杂度的做法，本题时间限制下调到 500 毫秒。\n\n## Note\n\n- 对于 $40\\%$ 的数据，$1 \\leq n \\leq 10^3$，对于每一个正整数 $i$，$1 \\leq i \\leq n$，都有 $1 \\leq a_i \\leq 10^9$。\n- 对于另外 $60\\%$ 的数据，$1 \\leq n \\leq 10^5$，对于每一个正整数 $i$，$1 \\leq i \\leq n$，都有 $1 \\leq a_i \\leq 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4241","tags":["二分","2025","北京","哈希 hashing","科创活动","小学活动"],"sample_group":[["4\n7 3 2 1","2"],["3\n1 1 1","3"]],"created_at":"2026-03-03 11:09:25"}}