CF1005C Summarize to the Power of Two

如果一个序列 $a_1, a_2, \dots, a_n$ 满足：对于每一个元素 $a_i$，都存在另一个元素 $a_j$（$i \ne j$），使得 $a_i + a_j$ 是 $2$ 的幂（即 $2^d$，其中 $d$ 为非负整数），则称该序列是“好”的。 例如，以下序列是“好”的： - $[5, 3, 11]$（例如，对于 $a_1=5$，可以选择 $a_2=3$，它们的和是 $2$ 的幂。同理，对于 $a_2$ 和 $a_3$ 也可以找到满足条件的元素）； - $[1, 1, 1, 1023]$； - $[7, 39, 89, 25, 89]$； - $[]$。 注意，根据定义，空序列（长度为 $0$）也是“好”的。 以下序列不是“好”的： - $[16]$（对于 $a_1=16$，无法找到另一个元素 $a_j$ 使得它们的和是 $2$ 的幂）； - $[4, 16]$（对于 $a_1=4$，无法找到另一个元素 $a_j$ 使得它们的和是 $2$ 的幂）； - $[1, 3, 2, 8, 8, 8]$（对于 $a_3=2$，无法找到另一个元素 $a_j$ 使得它们的和是 $2$ 的幂）。 给定一个序列 $a_1, a_2, \dots, a_n$，你需要删除最少数量的元素，使得剩下的序列是“好”的。你可以删除任意多个元素。

第一行包含一个整数 $n$（$1 \le n \le 120000$），表示给定序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

输出最少需要删除多少个元素，才能使给定序列变为“好”的。你可以选择删除全部 $n$ 个元素，使其变为空序列，此时也是“好”的。

在第一个样例中，只需删除一个元素 $a_4=5$，剩下的序列 $[4, 7, 1, 4, 9]$ 就是“好”的。 由 ChatGPT 4.1 翻译