← 返回题目列表

Codeforces · 1005/C

C. 总结为 2 的幂

中文机器翻译题面 查看原题

A sequence $$$a_1, a_2, \dots, a_n$$$ is called good if, for each element $$$a_i$$$, there exists an element $$$a_j$$$ ($$$i \ne j$$$) such that $$$a_i+a_j$$$ is a power of two (that is, $$$2^d$$$ for some non-negative integer $$$d$$$).

For example, the following sequences are good:

- $$$[5, 3, 11]$$$ (for example, for $$$a_1=5$$$ we can choose $$$a_2=3$$$. Note that their sum is a power of two. Similarly, such an element can be found for $$$a_2$$$ and $$$a_3$$$),
- $$$[1, 1, 1, 1023]$$$,
- $$$[7, 39, 89, 25, 89]$$$,
- $$$[]$$$.

请注意,根据定义,空序列(长度为 $$$0$$$)是好的。

For example, the following sequences are not good:

- $$$[16]$$$ (for $$$a_1=16$$$, it is impossible to find another element $$$a_j$$$ such that their sum is a power of two),
- $$$[4, 16]$$$ (for $$$a_1=4$$$, it is impossible to find another element $$$a_j$$$ such that their sum is a power of two),
- $$$[1, 3, 2, 8, 8, 8]$$$ (for $$$a_3=2$$$, it is impossible to find another element $$$a_j$$$ such that their sum is a power of two).

给你一个序列 $$$a_1, a_2, \dots, a_n$$$。 What is the minimum number of elements you need to remove to make it good?您可以删除任意一组元素。

输入

第一行包含整数 $$$n$$$ ($$$1 \le n \le 120000$$$) — 给定序列的长度。

第二行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

打印为了使给定序列良好而需要从给定序列中删除的元素的最小数量。您可能需要删除所有 $$$n$$$ 元素,将其清空,从而获得一个好的序列。

示例

输入 #1

6
4 7 1 5 4 9

输出 #1

1

输入 #2

5
1 2 3 4 5

输出 #2

2

输入 #3

1
16

输出 #3

1

输入#4

4
1 1 1 1023

输出#4

0

注意

在第一个示例中,删除一个元素 $$$a_4=5$$$ 就足够了。 The remaining elements form the sequence $$$[4, 7, 1, 4, 9]$$$, which is good.