Div3 codefores1005C Summarize to the Power of Two_综合

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 \neq 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]$ ,
$[]$ .

Note that, by definition, an empty sequence (with a length of $0$ ) is good.

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).

You are given a sequence $a_{1}, a_{2}, \dots, a_{n}$ . What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.

Input

The first line contains the integer $n$ ( $1 \leq n \leq 120000$ ) — the length of the given sequence.

The second line contains the sequence of integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

Output

Print the minimum number of elements needed to be removed from the given sequence in order to make it good. It is possible that you need to delete all $n$ elements, make it empty, and thus get a good sequence.

   Examples
  
     input
     
      Copy
     
6
4 7 1 5 4 9

     output
     
      Copy
     
1

     input
     
      Copy
     
5
1 2 3 4 5

     output
     
      Copy
     
2

     input
     
      Copy
     
1
16

     output
     
      Copy
     
1

     input
     
      Copy
     
4
1 1 1 1023

     output
     
      Copy
     
0

Note

In the first example, it is enough to delete one element $a_{4} = 5$ . The remaining elements form the sequence $[4, 7, 1, 4, 9]$

, which is good.

题意：给你一个数列，然后让你删掉最少的数，让每一个数都可以与另外一个数相加，之和等于2的^d次方，问最少删掉的个数

思路：暴力即可，先预处理出2的次幂，然后暴力出每个数与每个2的次幂之差，去判断在map中是否有这样的差存在（注意相同的两个数，比如4 ，4 这个时候就可以特判一下，出现次数）。（因为随手数组开了3000，RE了一发)

代码如下：

#include <bits/stdc++.h>using namespace std;const int maxn = 2e6;
map<long long,long long>m;
long long a[maxn];
int n;
long long d[40];int main() {d[0] = 1;for(int i = 1; i <= 31; i++) {d[i] = d[i - 1] * 2;}while(~scanf("%d",&n)) {m.clear();int cnt = 0;for(int i = 0; i < n; i++) scanf("%lld",&a[i]),m[a[i]]++;for(int i = 0; i < n; i++) {int flag = 0;for(int j = 0; j <= 31; j++) { if(a[i] >= d[j]) continue;else {int cha = d[j] - a[i];if(m[cha]) {if(a[i] == cha) {if(m[cha] > 1) {flag = 1;break;}} else {flag = 1;break ;}}}}if(!flag) cnt++;}cout << cnt << endl;}return 0;
}